어떻게 풀까?
최적화를 조금 많이하다보니 문제를 살짝 극혐으로 풀었습니다.
저는 DP, 슬라이딩 윈도도 함께 사용했습니다.
만약 슬라이딩 윈도를 잘 모르신다면
여기를 참고하세요
슬라이딩 윈도를 쓰는 이유!
이 문제를 잘 보시면 이전 년도의 나무들에 대한 정보는 전혀 필요가 없습니다.
따라서, 현재 년도와 다음 년도에 쓰일 공간만 필요한 것 입니다.
그림에서 보듯이 이전 년도의 나무 개수 자료는 전혀 쓰지 않습니다.
따라서 위처럼, 현재 나무들의 정보를 토대로 다음 년도의 나무를 저장하기 위해선 딱 2개의 정보 배열이 필요합니다.
2개의 나무 배열을 가지고 있다고 하면, y년 이라고 했을때, [y%2^1] 나무 배열을 현재 배열로, [y%2] 배열을 내년 배열로 쓰면 됩니닷!
그리고! 나무들의 정보들을 생각해봅시다.
기다려야 하는 년수가 1000을 넘지 않습니다.
즉, 나무들의 정보를 [x][y][age] 의 배열로 표현이 가능하다는 것 입니다! 공간 메모리는 2 * 10 * 10 * 1000 = 2e5가 되겠죠.
즉, (x,y,나이)의 나무들을 큐에 중복으로 넣지 않고 연산이 가능하다는 것이죠!
그럼 [x][y][age] 배열에 좌표가 (x,y)이고 나이가 age인 나무의 개수를 넣어놓으면, 죽은 나무와 살아남는 나무에 대한 처리가 쉬워집니다.
살아남은 나무들은 어떻게 표시할 수 있을까요??
-> 현재 (x,y)에 있는 양분 수 / 나이 입니다!
다만, 양분이 엄청나게 많을 수 있기 때문에, MIN( (x,y)의 양분 / 나이 , [x][y][age]인 나무의 개수) 가 살아남은 나무 수가 되겠죠!
예를 들어, (x,y) 좌표에 나무가 10살이고, 10살인 나무가 11그루가 있다고 합시다. (treenum[x][y][10] = 11)
양분이 88만큼 남아있다면 살아남을 수 있는 나무는 8그루 이죠! (88/10) = 8
만약, 나무가 7그루 였다면 살아남은 수 있는 나무는 MIN(8, 7) = 7 그루 입니다!
그렇다면 죽은 나무수는 어떻게 표시할 수 있을까요?
현재 살아남아있던 나무 수 - 살아남을 수 있는 나무 수 이겠죠.
위의 예로 다시 보면, 10살인 나무가 11그루 일때는 3그루가 죽고, 10살인 나무가 7그루일 때는 아무 나무도 죽지 않을 것입니다.
양분에는 살아남은 나무의 개수 * 나무의 나이 만큼 빼주면 되겠죠!
위의 10살인 나무가 11그루인 예에서는 양분이 8 남겠네요! (88-10*8)
8그루인 예에서는 18의 양분이 남습니다. (88-10*7)
자, 메모리를 쓰는 방법을 알아보았으니이제 구현 부분으로 넘어갑시다.
이 문제는 봄, 여름, 가을, 겨울에 대한 처리를 시뮬레이션 하는것이 매우 중요합니다!
다만, 순서가 꼭 봄, 여름, 가을, 겨울일 필요는 없습니다.
해야할 일을 나열해 봅시다.
1. 봄 - 나무들이 양분을 먹고 자라난다. 못먹으면 죽는다.
2. 여름 - 죽은 나무들이 양분이 된다.
3. 가을 - 나무들이 번식을 한다.
4. 겨울 - 주어진 양분들을 더한다.
봄은 가장 먼저 처리해야하는 것은 맞습니다.
하지만, 이후에 여름이나 가을, 겨울의 일들은 순서가 언제 일어나더라도 크게 상관이 없습니다!
이미 이번년도에 봄에 양분에 대한 처리가 완료되었고,
여름에 다시 양분이 생겨도 이미 봄에 나무들이 양분을 모두 먹었고,
가을에 나무가 번식을 해도, 새로운 나무가 양분을 소모하는 것은 내년 일이기 때문이죠!
겨울에 양분이 다시 더해져도 여름과 마찬가지로 이미 올해의 양분은 모두 소모되었기 때문에 어디에도 영향을 주지 않습니다.
따라서, 일의 처리를 다음과 같은 순서로 하도록 하겠습니다.
- 전년도에 살아남았던 나무들에 대해 아래 과정을 처리한다.
- 살아남는 나무와 죽은 나무 수를 구한다.(봄)
- 살아남은 나무들이 있을경우 : 나무들이 자라서 5의 배수가 된다면, 해당 나무 8방향에 나이 1살의 나무들을 심는다.(가을)
- 죽은 나무들이 있을 경우 : 죽은 나무들의 나이와 수를 저장한다.
- 저장된 죽은 나무들을 양분으로 만든다. (여름)
- 양분을 더한다. (겨울)
앗! 근데 중요한것이 빠졌습니다.
양분을 먹을 때 "나이"가 작은 나무부터 양분을 먹어야 한다는 것 입니다!
어짜피 이전에 빠르게 처리됐던 나무라면, 다음에도 빠르게 처리되기 때문입니다.
나무의 나이는 모두 1살씩 늘어나니까요!
즉, 먼저 처리되는 나무는 다시 다음 배열의 뒷부분에 차곡차곡 쌓으면 됩니다.
다만, 문제가 생기는 부분이 있습니다.
바로 나무가 5살이 되는 때 입니다.
하지만.. 생각보다 이를 처리하기 쉽습니다.
5살이 되는 나무들은 1살 나무들을 앞에 처리하면 되기 때문이죠!
이를 위해서 deque라는 자료 구조를 사용합시다!!
앞에서도 뒤에서도 넣을 수 있는 자료 구조이죠.
이렇게 하면, 맨 처음 deque만 나이순으로 정렬해 주면 언제나 나이순으로 정렬된 deuqe이 존재합니다.
그리고, 맨 처음에는 [X][Y][나이]를 통하여 deque에 겹치지 않게 나무의 상태를 보관한다고 했습니다.
하지만, 나무의 나이가 5의 배수가 되면 8 방향에 나이가 1인 나무가 생기기 때문에 나무의 수가 겹칠 수도 있습니다.
이럴땐 어떻게 해야할까요??
BFS에서 visit을 처리하는 경우와 비슷하게 처리하면 됩니다.
treenum[X][Y][1] 이 0이라는 것은, 현재 큐 안에 (x,y)에 나무 1인 좌표가 없다는 의미입니다.
따라서, 이 경우에는 treenum[x][y][1]에 현재 나무의 개수로 만들어주고 큐에 좌표와 나이도 넣습니다!
반대로 treenum[x][y][1]이 0이 아니라면, 이미 다음 큐에는 해당 나무 정보가 들어있다는 것 입니다!
따라서 treenum[x][y][1]에 자신의 나무수를 더하는 것으로 함수를 끝냅니다.
큐 안에 중복 나무는 없으면서 나무의 수는 제대로 유지되는 것을 확인할 수 있습니다!
현재까지 설명한 것을 코드로 나타내 봅시다!
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 | int info[2][10][10][1011]; int food[10][10]; int winter[10][10]; struct TREE { int r, c, age, num; TREE() :r(0), c(0) { } TREE(int r, int c) : r(r), c(c) {} }; void go(int y) { int next = y % 2; int cur = next ^ 1; for(int i = 0; i < spring[cur].size(); i++) { TREE now = spring[cur][i]; int remain = food[now.r][now.c]; int tnum = info[cur][now.r][now.c][now.age]; //나무 수 int lnum = remain / now.age; //살 수 있는 나무 수 lnum = lnum > tnum ? tnum : lnum; int dnum = tnum - lnum; //죽은 나무 수 //봄 food[now.r][now.c] -= lnum * now.age; if (dnum) { TREE dead = now; dead.num = dnum; summer.push(dead); } if (lnum) { //가을 if ((now.age + 1) % 5 == 0) { for (int d = 0; d < 8; d++) { TREE child = now; child.r += dr[d]; child.c += dc[d]; child.age = 1; if (isout(child.r, child.c)) continue; if (info[next][child.r][child.c][1] == 0) spring[next].push_front(child); info[next][child.r][child.c][1] += lnum; } } TREE live = now; live.age++; spring[next].push_back(live); } info[next][now.r][now.c][now.age + 1] = lnum; info[cur][now.r][now.c][now.age] = 0; } //여름 while (summer.size()) { TREE now = summer.front(); summer.pop(); food[now.r][now.c] += (now.age / 2)*now.num; } spring[cur].clear(); //겨울 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) food[i][j] += winter[i][j]; } | cs |
현재 년도에 있던 나무의 자리 수는 2년 뒤에 또 써야하기 때문에 다음 년도로 넘어가기 전에 0 으로 초기화하는 것을 잊지 맙시다!
이제 남은 일은 이 일을 k번 반복 하는 것입니다.
코드
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 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | #include<iostream> #include<deque> #include<queue> using namespace std; int info[2][10][10][1011]; int food[10][10]; int winter[10][10]; struct TREE { int r, c, age, num; TREE() :r(0), c(0) { } TREE(int r, int c) : r(r), c(c) {} }; int n, m, k; int dr[] = { -1,-1,-1,0,0 ,1,1,1 }; int dc[] = { -1,0,1,-1,1,-1,0,1 }; inline bool isout(int r, int c) { return r < 0 || c < 0 || r >= n || c >= n; } deque<TREE> spring[2]; queue<TREE> summer; void go(int y) { int next = y % 2; int cur = next ^ 1; for(int i = 0; i < spring[cur].size(); i++) { TREE now = spring[cur][i]; int remain = food[now.r][now.c]; int tnum = info[cur][now.r][now.c][now.age]; //나무 수 int lnum = remain / now.age; //살 수 있는 나무 수 lnum = lnum > tnum ? tnum : lnum; int dnum = tnum - lnum; //죽은 나무 수 //봄 food[now.r][now.c] -= lnum * now.age; if (dnum) { TREE dead = now; dead.num = dnum; summer.push(dead); } if (lnum) { //가을 if ((now.age + 1) % 5 == 0) { for (int d = 0; d < 8; d++) { TREE child = now; child.r += dr[d]; child.c += dc[d]; child.age = 1; if (isout(child.r, child.c)) continue; if (info[next][child.r][child.c][1] == 0) spring[next].push_front(child); info[next][child.r][child.c][1] += lnum; } } TREE live = now; live.age++; spring[next].push_back(live); } info[next][now.r][now.c][now.age + 1] = lnum; info[cur][now.r][now.c][now.age] = 0; } //여름 while (summer.size()) { TREE now = summer.front(); summer.pop(); food[now.r][now.c] += (now.age / 2)*now.num; } spring[cur].clear(); //겨울 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) food[i][j] += winter[i][j]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> k >> m; for (register int i = 0; i < n; i++) for (register int j = 0; j < n; j++) { cin >> winter[i][j]; food[i][j] = 5; } while (k--) { TREE tree; cin >> tree.r >> tree.c >> tree.age; tree.r--, tree.c--; spring[m % 2].push_back(tree); info[m % 2][tree.r][tree.c][tree.age]++; } while (m--) go(m); int res = 0; while (spring[0].size()) { TREE now = spring[0].front(); spring[0].pop_front(); res += info[0][now.r][now.c][now.age]; } cout << res; return 0; } | cs |
시간 복잡도
시간복잡도는 최악의 경우에 큐 안에 N*N*max(나이)가 k번 반복되는 경우입니다.
즉, 
'공부 > 알고리즘 문제풀이' 카테고리의 다른 글
| [삼성 기출 문제] 백준 5373 큐빙 (23) | 2019.03.13 |
|---|---|
| [삼성 기출 문제] 백준 16236 아기 상어 (0) | 2019.03.12 |
| [삼성 기출 문제] 백준 16234 인구 이동 (2) | 2019.03.12 |
| [삼성 기출 문제] 백준15686 치킨 배달 (0) | 2019.03.12 |
| [삼성 기출 문제] 백준15685 드래곤 커브 (0) | 2019.03.11 |
