-
백준 16235번 나무 재테크PS 2020. 2. 7. 23:53
https://www.acmicpc.net/problem/16235
<접근방법>
시뮬레이션 문제입니다.
풀면서 자료구조 선택이 승패를 좌우하겠구나 생각했습니다.
나무에 대한 정보, 현재 양분에 대한 정보, 뿌리는 양분에 대한 정보, 죽은 나무에 대한 정보를
보관해야합니다.
나무에 대한 정보의 경우, 나무가 여러 개 겹칠 수 있고, 얼마나 겹칠지 알 수가 없습니다.
그래서 이차원 배열 벡터로 구현하였습니다.
현재 양분, 뿌리는 양분에 대한 정보는 이차원 배열로 하였습니다.
죽은 나무의 상태는 좌표마다 달라집니다. 그래서 초기화만 신경써주면 뭘 해도 상관없습니다.
보통 큐나 매개변수 사용이 초기화에 대한 걱정을 없애줍니다.
나무의 이차원 배열 벡터에서 죽은 나무를 빼는 것을 갯수 카운팅으로 처리하였습니다.
구현하면서도 너무 위험한 방법이라고 생각했으나, 급한 마음에 그냥 했습니다.
다른 분 코드를 보니 살아남은 친구들을 임시의 공간에 저장하고
해당 좌표의 나무 공간을 싹 비운 다음, 살아남은 친구들만 넣어주었습니다.
왜 이 생각을 못했을까...
구현이 힘들거나 위험하면 메모리를 더 쓸 생각을 해보자!
<코드>
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; struct info { int y, x, age; }; int n, m, k; int lunch[10][10], map[10][10]; int dy[8] = {1, -1, 0, 0, 1, 1, -1, -1}; int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1}; vector<int> tree[10][10]; queue<info> die; int cal() { int res = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { res += tree[i][j].size(); } } return res; } void spring() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int sz = tree[i][j].size(); if (sz == 0) continue; sort(tree[i][j].begin(), tree[i][j].end()); int alive = 0; for (int u = 0; u < sz; u++) { int t = tree[i][j][u]; if (map[i][j] >= t) { map[i][j] -= t; tree[i][j][u]++; alive++; } else { die.push({i, j, t}); } } tree[i][j].erase(tree[i][j].begin() + alive, tree[i][j].end()); } } } void summer() { while (!die.empty()) { info t = die.front(); die.pop(); map[t.y][t.x] += (t.age/2); } } void fall() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int u = 0; u < tree[i][j].size(); u++) { if (tree[i][j][u] % 5 == 0) { for (int d = 0; d < 8; d++) { int ty = i + dy[d]; int tx = j + dx[d]; if (ty < 0 || ty >= n || tx < 0 || tx >= n) continue; tree[ty][tx].push_back(1); } } } } } } void winter() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { map[i][j] += lunch[i][j]; } } } void simul() { while (k--) { //봄 spring(); //여름 summer(); //가을 fall(); //겨울 winter(); } } int main() { cin >> n >> m >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> lunch[i][j]; map[i][j] += 5; } } for (int i = 0; i < m; i++) { int a, b, c; cin >> b >> a >> c; b--; a--; tree[b][a].push_back(c); } simul(); cout << cal() << '\n'; return 0; }
<느낀 점>
-구현이 힘들거나 위험하면 메모리를 더 쓸 생각을 해보자!
'PS' 카테고리의 다른 글
백준 16918번 봄버맨 (0) 2020.02.09 백준 16234번 인구 이동 (0) 2020.02.07 백준 16236번 아기상어 (0) 2020.02.07 백준 17144번 미세먼지 안녕! (0) 2020.02.07 백준 12100번 2048(Easy) (0) 2020.02.06