짬뽕얼큰하게의 맨땅에 헤딩 :: '알고리즘' 카테고리의 글 목록 (26 Page)

프로그래머스 (Programmers) 입국심사

알고리즘 2021. 1. 12. 00:19

입국심사.

처음엔 당황했지만.. 생각해보니 풀 수 있었다.

이분탐색 문제라는걸 몰랐으면 더 힘들었을 것 같다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <string>
#include <vector>
 
using namespace std;
 
long long solution(int n, vector<int> times) {
    long long answer = 1000000000000000000;
    long long l = 1;
    long long r = answer;
 
    while (l <= r) {
        long long mid = (l + r) / 2;
        int simsa = times.size();
        long long person = 0;
        for (int i = 0; i < simsa; i++) {
            person += mid / times[i];
        }
        if (person >= n) {
            answer = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
 
    return answer;
}
cs

'알고리즘' 카테고리의 다른 글

Redundant Connection  (0) 2025.02.01
프로그래머스 (PROGRAMMERS) 문자열압축  (0) 2021.01.18
프로그래머스 (Programmers) 가장 먼 노드  (0) 2021.01.11
프로그래머스 (Programmers) 섬 연결하기  (0) 2021.01.11
프로그래머스(programmers) N으로 표현  (0) 2021.01.11
블로그 이미지

짬뽕얼큰하게

,

프로그래머스 (Programmers) 가장 먼 노드

알고리즘 2021. 1. 11. 23:44

BFS 이용해서 풀었다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <string>
#include <vector>
#include <queue>
 
using namespace std;
bool visited[20001];
vector<int> link[20001];
struct _pair {
    int num;
    int cnt;
};
queue<_pair> que;
int maxCnt = 0;
int solution(int n, vector<vector<int>> edge) {
    int answer = -1;
    int edgeN = edge.size();
    for (int i = 0; i < edgeN; i++) {
        int a = edge[i][0];
        int b = edge[i][1];
        link[a].push_back(b);
        link[b].push_back(a);
    }
    visited[1] = true;
    que.push({ 1, 0 });
    while (!que.empty()) {
        _pair pair = que.front();
        que.pop();
        if (pair.cnt > maxCnt) {
            maxCnt = pair.cnt;
            answer = 1;
        }
        else if (pair.cnt == maxCnt) {
            answer++;
        }
        for (int i = 0; i < link[pair.num].size(); i++) {
            int a = pair.num;
            int b = link[a][i];
            if (visited[b]) continue;
            visited[b] = true;
            que.push({ b,pair.cnt + 1 });
        }
    }
 
    return answer;
}
cs

'알고리즘' 카테고리의 다른 글

프로그래머스 (PROGRAMMERS) 문자열압축  (0) 2021.01.18
프로그래머스 (Programmers) 입국심사  (0) 2021.01.12
프로그래머스 (Programmers) 섬 연결하기  (0) 2021.01.11
프로그래머스(programmers) N으로 표현  (0) 2021.01.11
[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
블로그 이미지

짬뽕얼큰하게

,

프로그래머스 (Programmers) 섬 연결하기

알고리즘 2021. 1. 11. 23:06

크루스칼로 풀었다.

/**

실수:

disjoint함수의 두 a,b값이 다른 경우 uf[disjoint(a)] = disjoint(b); 최상위 번호를 찾아 넣어줘야하는데...

uf[a] = disjoint(b) 로 넣어주었다.. ㅠㅠ

이렇게 되면 두집합이 합쳐질때 최상위번호가 바뀌는게 아니라.. 중간쯔음에서 바뀌기 때문에... 집합 전체가 합쳐지지 않는다.

오히려 이건 가능하다.

uf[disjoint(a)] = b

b는 최상위가 아니여도... a의 최상위를 b로 바꿔주었기때문에.. disjoint 함수를 부르게되면 최상위 번호로 갱신된다.


**/



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[2] < b[2];
}
int uf[100];
int disjoint(int x) {
    if (uf[x] == x) return x;
    return uf[x] = disjoint(uf[x]);
}
int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    for (int i = 0; i < n; i++) {
        uf[i] = i;
    }
 
    int row = costs.size();
 
    sort(costs.begin(), costs.end(), &cmp);
 
    for (int i = 0; i < row; i++) {
        int a = costs[i][0];
        int b = costs[i][1];
        int cost = costs[i][2];
        if (disjoint(a) != disjoint(b)) {
            uf[disjoint(a)] = disjoint(b);
            answer += cost;
        }
        else {
            continue;
        }
    }
 
    return answer;
}
 
cs


'알고리즘' 카테고리의 다른 글

프로그래머스 (Programmers) 입국심사  (0) 2021.01.12
프로그래머스 (Programmers) 가장 먼 노드  (0) 2021.01.11
프로그래머스(programmers) N으로 표현  (0) 2021.01.11
[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
블로그 이미지

짬뽕얼큰하게

,

프로그래머스(programmers) N으로 표현

알고리즘 2021. 1. 11. 22:49

프로그래머스(programmers) N으로 표현

/**
1. 빼기와 나누기의 경우 순서가 바뀌는경우 결과값이 달라진다.
처음에 최적화를 한답시고, i/2+1 까지만 돌렸다가, WA를 받았다. 
이 점을 확인 한 후 i-1까지 돌렸다.

2. newN(222,333,44444) 의 숫자를 만들고.... 만들어야 하는 최종 숫자와 비교를 하지 않았다.
단순한 실수인데... 반례를 찾느라 한시간이 걸렸다. ㅜㅜ
구현 도중에도 검사해야겠다는 생각을 하지 않았다.;;;;;;;;;;;;
**/

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <string>
#include <vector>
using namespace std;
 
vector<int> v[9];
int solution(int N, int number) {
    if (N == number) return 1;
    for (int i = 0; i < 9; i++) {
        v[i].clear();
    }
    int newN = N;
    v[1].push_back(N);
    for (int i = 2; i < 9; i++) {
        newN = 10 * newN + N;
        v[i].push_back(newN);
        if (newN == number) return i;
 
        for (int j = 1; j < i; j++) {
            for (int a = 0; a < v[i - j].size(); a++) {
                for (int b = 0; b < v[j].size(); b++) {
                    if (v[i - j][a] == 0 || v[j][b] == 0) continue;
                    int res = v[i - j][a] + v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
 
                    res = v[i - j][a] - v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
 
                    res = v[i - j][a] * v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
 
                    if (v[j][b] == 0) continue;
                    res = v[i - j][a] / v[j][b];
                    v[i].push_back(res);
                    if (res == number) return i;
                }
            }
        }
    }
    return -1;
}
cs

'알고리즘' 카테고리의 다른 글

프로그래머스 (Programmers) 가장 먼 노드  (0) 2021.01.11
프로그래머스 (Programmers) 섬 연결하기  (0) 2021.01.11
[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
알고스팟 (algospot) FORTRESS  (1) 2019.01.26
블로그 이미지

짬뽕얼큰하게

,

[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수

알고리즘 2020. 12. 28. 15:21

1. 자료구조:


1
2
3
4
5
6
7
8
9
10
11
struct student{
 
char name[2];
 
unsigned long nameKey;
 
};
 
 
 
student gAllStudent[100];
cs

 


2. hash 함수: unsigned long getNameKey(char* name);



위와 같은 상황에서 이름의 hash값을 이용하여 gAllStudent에 있는 여러명의 학생 이름을 빠르게 찾을 때 한 실수다.


name1, name2 를 찾는다 했을때, getNameKey로 얻은 hash값을 nameKey1, nameKey2라고 하면


1
2
3
4
5
6
7
8
9
 
 for(int i = 0 ; i < 100; i++) {
  if (gAllStudent[i].nameKey == nameKey1) {
    if(strcmp(gAllStudent[i].name, name1) == 0) { ~~~~}
  }
  else if(gAllStudent[i].nameKey == nameKey2) {
    if(strcmp(gAllStudent[i].name, name2) == 0) { ~~~~}
  }
}

cs

 



위와 같이 작성했다..

그런데.. hash값이기 때문에, name1, name2이름은 다르고 nameKey1과 nameKey2 가 같은 경우가 존재한다.


이런 경우 name2도 첫번째 if문만 들어가기때문에... 문제가 발생한다. 따라서 else if문을 if문으로 변경하여 가볍게 해결할 수있다.


위 실수를하여.. 원인 분석에 꽤 많은 시간이 들어 정리해 놓는다.






'알고리즘' 카테고리의 다른 글

프로그래머스 (Programmers) 섬 연결하기  (0) 2021.01.11
프로그래머스(programmers) N으로 표현  (0) 2021.01.11
Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
알고스팟 (algospot) FORTRESS  (1) 2019.01.26
백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
블로그 이미지

짬뽕얼큰하게

,

Visual Studio Code (VS Code) PS용 환경설정

알고리즘 2019. 2. 7. 12:12

VS Code Problem Solving용 환경설정


작업 당시 운영체제: Ubuntu 18.04 64bit


VS Code를 활용하여 백준, 알고스팟, 코드 포스 등 여러 문제를 풀기위한 간단한 환경설정들이 검색해도 나오지 않아, 여기에 정리한다.


내가 VS 코드를 처음 설치하고 부딪힌 문제는 총 두개이다.

1. 어떻게 실행하지? -> Code Runner 이용

2. 인풋을 어떻게 입력하지? -> 설정 변경


1. VS Code 설치 : 생략


2. extension의 C/C++ 설치

   나는 C/C++ 를 사용하므로 해당 extension을 설치하였다.


3. code runner 설치

   빌드 및 실행하기 위한 code runner 설치


4. File -> preference -> setting에 들어 간 후

extensions -> Run Code configuration -> Run In Terminal checking!!!


5. 마우스 오른쪽 클릭, Run Code를 통해 실행


6. 터미널창에 입력이 가능한지 확인



VS Code를 사용하기위한 5분 설정 팁이다. Code Runner만 설치하여 사용할 시 output에 실행 결과가 나타나게 되는데, 이 output창에는 입력을 넣을 수가 없다.


따라서 PS를 위한 입력을 주기위해서는 위와 같은 세팅을 통해, 터미널에서 실행하는 것으로 변경 해야한다.


나도 시행착오 끝에 알아낸 방법인데, 

더 좋은 방법이 있다면 댓글로 정보 공유 부탁드립니다.  :D



'알고리즘' 카테고리의 다른 글

프로그래머스(programmers) N으로 표현  (0) 2021.01.11
[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
알고스팟 (algospot) FORTRESS  (1) 2019.01.26
백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
블로그 이미지

짬뽕얼큰하게

,

알고스팟 (algospot) FORTRESS

알고리즘 2019. 1. 26. 18:34

못풀었다.

종만북 코드를 이해하고 책을 보지않고 따라해보았다.


leaf에서 leaf까지의 최대값과 leaf에서 root까지의 최대값의 최대값이 정답이 되는것으로 나눈것을 생각하지 못했다. 더 깊이 생각하는 습관을 가져야겠다.


트리 탐색시 다음노드들의 리턴값을 벡터에 저장하여 높이를 뽑아내는 패턴도 기억 해야겠다는 생각을 했다.


트리 탐색 기본 구조도 익혔고, 트리 생성 기본 구조도 익힐 수 있었다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Pair{
    int y;
    int x;
    int r;
};
struct TreeNode{
    vector<TreeNode*> children;
};
 
 
Pair wall[101];
int longest;
int N, T;
 
int sq(int x){
    return x * x;
}
bool enclose(int a, int b){
    if(wall[a].r <= wall[b].r) return false;
 
    int y1 = wall[a].y;
    int x1 = wall[a].x;
    int r1 = wall[a].r;
    int y2 = wall[b].y;
    int x2 = wall[b].x;
    int r2 = wall[b].r;
    if(sq(r1 - r2) <= sq(x1 - x2) + sq(y1 - y2)){
        return false;
    }
    return true;
}
 
bool isChild(int parent, int child){
    if(parent == child) return false;
    if(!enclose(parent, child)) return false;
    for(int i = 0 ; i < N; i++){
        if(i == parent || i == child) continue;
        if(enclose(parent, i) && enclose(i, child)) return false;
 
    }
    return true;
}
TreeNode* getTree(int root){
    TreeNode* node = new TreeNode();
    for(int i = 0 ; i < N; i++){
        if(isChild(root, i)){
            node->children.push_back(getTree(i));
        }
    }
 
    return node;
}
 
 
int height(TreeNode* root){
    int s = root->children.size();
    vector<int> heights;
    for(int i = 0 ; i < s; i++){
        heights.push_back(height(root->children[i]));
    }
    if(heights.empty()) return 0;
    int h_s = heights.size();
    if(h_s >= 2){
        sort(heights.begin(), heights.end());
        longest = max(longest, heights[h_s - 1] + heights[h_s - 2] + 2);
    }
    return heights.back() + 1;
}
bool cmp(Pair a, Pair b){
    if(a.r < b.r) return false;
 
    return true;
}
 
int main(void){
    scanf("%d", &T);
    while(T--){
        longest = 0;
        scanf("%d", &N);
        for(int i = 0 ; i < N; i++){
            int x, y, r;
            scanf("%d %d %d", &x, &y, &r);
            wall[i] = {y, x, r};
        }
 
        sort(wall, wall + N, cmp);
 
 
        TreeNode* root = getTree(0);
        printf("%d\n", max(longest, height(root)));
    }
}
cs


'알고리즘' 카테고리의 다른 글

[논리 오류] 한번의 for문으로 여러 데이터의 hash값을 처리시 한 실수  (0) 2020.12.28
Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 16234 - 인구이동

알고리즘 2019. 1. 21. 22:59

영역 구하기 응용문제였던 것 같다.

인접한 지역과의 차가 L이상 R 이하인 영역을 벡터에 담고,

담긴 벡터들 값의 평균을 구해 이동된 다음 맵을 만드는 방법을 선택했다.


때문에 맵을 map[50][50][2]형태로 선언하였고,  두맵을 번갈아 가며 사용하게된다.


 방문배열은 매번 초기화 하는 비용을 없애고 싶어서 int형으로 선언하여 이동한 날짜수를 기록해주었다.


사실 인접한 지역을 구하면서 sum값을 구하면 더 효율적인 코드게 되겠지만, 결국 시간복잡도에서는 차이가 없을 것 같아 편하게 답을 구하는쪽으로 코딩했다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
using namespace std;
 
struct _pair{
    int y;
    int x;
};
int N, L, R;
int map[50][50][2];
int visited[50][50];
int k;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int abs(int a){
    if(a < 0) a *= -1;
    return a;
}
void check(int y, int x, vector<_pair>& v){
    visited[y][x] = k;
 
    for(int i = 0 ; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx] >= k){
            continue;
        }
        int n = abs(map[y][x][k%2] - map[ny][nx][k%2]);
        if(n >= L && n <= R){
            check(ny, nx, v);
            v.push_back({ny, nx});
        }
    }
}
int main(void){
    scanf("%d %d %d", &N, &L, &R);
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            scanf("%d", &map[i][j][k]);
            visited[i][j] = -1;
        }
    }
 
    while(true){
        bool result = false;
        vector<_pair> v;
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                if(visited[i][j] >= k) continue;
                check(i, j, v);
                int n = v.size();
                if(n > 0) result = true;
                int t_sum = map[i][j][k%2], t_cnt = 1 + n;
                for(int l = 0; l < n; l++){
                    int y = v[l].y;
                    int x = v[l].x;
                    t_sum += map[y][x][k%2];
                }
                int value = t_sum / t_cnt;
                for(int l = 0; l < n; l++){
                    int y = v[l].y;
                    int x = v[l].x;
                    map[y][x][(k + 1)%2] = value;
                }
                map[i][j][(k + 1)%2] = value;
                v.clear();
            }
        }
        if(!result) break;
        k++;
    }
 
 
    printf("%d", k);
 
}
cs


'알고리즘' 카테고리의 다른 글

Visual Studio Code (VS Code) PS용 환경설정  (1) 2019.02.07
알고스팟 (algospot) FORTRESS  (1) 2019.01.26
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
백준(BOJ) 1475 - 방번호  (0) 2019.01.02
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 16236 - 아기 상어

알고리즘 2019. 1. 21. 20:26

아기상어 문제를 풀었다.

하반기에 한번 풀어본 문제여서 같은 방법으로 접근했다.


bfs로 먹을수 있는 물고기를 탐색한 다음 소팅하여 가장 우선순위가 높은 물고기를 선택하였다.

조건들만 잘 넣어준다면, 어렵지 않게 풀수 있는 문제이다.


풀고 나서 생각이 든 것인데, 가장 우선순위가 높은 하나만 선택하면 되기때문에

덱을 사용하여  비어있거나 0번 인덱스 물고기보다 우선순위가 낮은 물고기는 뒤에 푸쉬하고 우선순위가 높은 물고기는 앞에 푸쉬를 한면, 소팅을 안해도 될 것 같다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct _pair{
    int y;
    int x;
    int cnt;
 
};
 
bool cmp(_pair a, _pair b){
    if(a.cnt < b.cnt) return true;
    if(a.cnt == b.cnt){
        if(a.y < b.y) return true;
        if(a.y == b.y){
            if(a.x < b.x) return true;
        }
    }
 
    return false;
}
int N;
int shark_y, shark_x, shark_size, eat_cnt, total_second;
int map[21][21];
 
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool bfs(vector<_pair>& fishes){
    queue<_pair> q;
    bool visited[21][21];
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            visited[i][j] = false;
        }
    }
    visited[shark_y][shark_x] = true;
    q.push({shark_y, shark_x, 0});
    while(!q.empty()){
        _pair p = q.front();
        q.pop();
        for(int i = 0 ; i < 4; i++){
            int ny = p.y + dy[i];
            int nx = p.x + dx[i];
            if(ny < 0 || ny >= N || nx < 0 || nx >= N
                || visited[ny][nx] || map[ny][nx] > shark_size){
                continue;
            }
            visited[ny][nx] = true;
            q.push({ny,nx,p.cnt + 1});
            if(map[ny][nx] > 0 && map[ny][nx] < shark_size){
                fishes.push_back({ny, nx, p.cnt + 1});
            }
 
        }
    }
    if(fishes.size() > 0) return true;
    return false;
}
 
int main(void){
    scanf("%d", &N);
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            scanf("%d", map[i] + j);
            if(map[i][j] == 9){
                shark_y = i;
                shark_x = j;
                shark_size = 2;
                map[i][j] = 0;
            }
        }
    }
    vector<_pair> fishes;
    while(bfs(fishes)){
        sort(fishes.begin(), fishes.end(), cmp);
        shark_y = fishes[0].y;
        shark_x = fishes[0].x;
        total_second += fishes[0].cnt;
        eat_cnt++;
        map[shark_y][shark_x] = 0;
        if(eat_cnt == shark_size){
            eat_cnt = 0;
            shark_size++;
        }
        fishes.clear();
    }
    printf("%d", total_second);
 
}
cs


'알고리즘' 카테고리의 다른 글

알고스팟 (algospot) FORTRESS  (1) 2019.01.26
백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16235 - 나무 재테크  (0) 2019.01.15
백준(BOJ) 1475 - 방번호  (0) 2019.01.02
백준(BOJ) 10250 - ACM 호텔  (0) 2019.01.02
블로그 이미지

짬뽕얼큰하게

,

백준(BOJ) 16235 - 나무 재테크

알고리즘 2019. 1. 15. 20:11

시뮬레이션 문제였다.

작년 하반기에 삼성 시험에서 이 문제를 풀때 스택을 사용하면, 최근에 추가한 나무가 가장 나이가 어리기 때문에 이 방법을 이용하여 넣었다 뺐다 하다가 시간초과가 났던 것이 기억났다.


이번에도 스택을 이용해서 풀자고 생각해서, 스택을 이용해서 깔끔하게 푼것 같았다. 예제케이스도 나와서 정말 깔끔하군! 생각했는데, AC를 받지 못했다.


스택을 사용하면 가장 어린놈을 순서대로 빼낼수 있다는 옜날 생각을 그대로 적용했던 것이 실수였다. 다시 생각해보니 시험당시에는 어린 순서를 맞춰주기 위해 스택하나를 더 두고 빼면서 임시스택에 넣고 결과값을 다시 스택에 저장하는 방법을 사용했다. 이 생각을 잊은채 걍 스택쓰면 되긴 했었는데? 라는 생각으로 스택을 썼고 계속 왜틀렸지만 반복했다.

이러니 그때 시간초과가 났지...


나이가 어린순을 유지하기위해 덱 자료구조를 이용했다.

가을에 추가되는 나무들은 push_back 으로 덱에 저장하고, 봄에 양분을 먹고 한살 더 자라날때에는 push_front로 앞에 추가해주어 나이 순서를 유지시켜주었다.


덱 자료구조를 tree[11][11][1001] 만큼 선언했는데, 사실 tree[11][11][2] 면 충분하다.

k를 %2연산하여 공간을 활용할 수 있지만 귀찮아서... 걍 했다.


tree변수에는 각 지역에 해당하는 나무들의 나이가 저장되어있다.

provide에는 입력으로 주어지는 겨울에 공급되는 양분의 양이 저장되어있다.

die[11][11] 에는 봄에 죽은나무 나이 /2 한값을 저장해 놨다가 여름에 더해준다.

fall[11][11]은 봄에 나이를 한살 먹고 5의 배수가 되는 나무들의 수가 저장되고, 가을에 이 수만큼 한살짜리 나무들을 주변에 추가해준다.


덱을 사용하니 200ms이 나왔다. 삼성은 통과할 수준이지만, 많이 느린 방법이다. 

정답을보니 갓님들의 풀이가 많이 보였다. 시간날때 하나씩 봐야겠다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <deque>
 
using namespace std;
int N, M, K;
int provide[11][11];
int map[11][11];
 
deque<int> tree[11][11][1001];
int die[11][11];
int fall[11][11];
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
 
 
int main(void){
   scanf("%d %d %d", &N, &M, &K);
 
   for(int i = 1; i <= N; i++){
       for(int j = 1 ; j <= N; j++){
            scanf("%d", provide[i] + j);
            map[i][j] = 5;
       }
   }
 
   for(int i = 0 ; i < M; i++){
        int r, c, a;
        scanf("%d %d %d", &r, &c, &a);
        tree[r][c][0].push_front(a);
   }
 
 
   for(int k = 0 ; k < K; k++){
       for(int i = 1; i <= N; i++){
           for(int j = 1 ; j <= N; j++){
                while(!tree[i][j][k].empty()){
                    int age = tree[i][j][k].back();
                    tree[i][j][k].pop_back();
                    if(age <= map[i][j]){
                        map[i][j] -= age;
                        tree[i][j][k+1].push_front(age + 1);
 
                        if((age + 1) % 5 == 0){
                            fall[i][j]++;
                        }
 
                    }
                    else{
                        die[i][j] += age/2;
                    }
                }
 
 
           }
       }
       for(int i = 1 ; i <= N; i++){
           for(int j = 1 ; j <= N; j++){
               map[i][j] += die[i][j];
               die[i][j] = 0;
               for(int l = 0; l < fall[i][j]; l++){
                   for(int m = 0; m < 8; m++){
                       int ni = i + dy[m];
                       int nj = j + dx[m];
                       if(ni > 0 && ni <= N && nj > 0 && nj <= N ){
                            tree[ni][nj][k + 1].push_back(1);
                       }
                   }
               }
               fall[i][j] = 0;
 
               map[i][j] += provide[i][j];
           }
       }
 
 
   }
   int cnt = 0 ;
   for(int i = 1 ; i <= N; i++){
       for(int j = 1 ; j <= N; j++){
           cnt += tree[i][j][K].size();
       }
   }
    printf("%d\n", cnt);
 
 
}
 
cs


'알고리즘' 카테고리의 다른 글

백준(BOJ) 16234 - 인구이동  (0) 2019.01.21
백준(BOJ) 16236 - 아기 상어  (0) 2019.01.21
백준(BOJ) 1475 - 방번호  (0) 2019.01.02
백준(BOJ) 10250 - ACM 호텔  (0) 2019.01.02
백준(BOJ) 2293 - 동전1  (0) 2019.01.02
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

티스토리툴바