백준 16235번 _나무 재테크
https://www.acmicpc.net/problem/16235
1. 풀이방법
이 문제는 구현이 어렵다기보단 구현을 하기전 어떤 자료형을 쓸것인지에 대해서 많은 고민이 되는 문제였다.
처음에는 양분에 대한 배열, 겨울에 추가할 양분에 대한 배열, 나무의 개수에 대한 배열, 나무의 데이터에 대한 map
다 따로 만들어 풀었다.
하지만, 계속된 시간초과로 인해 인터넷을 참고해 나무의 개수, 나무의 데이터를 합친 vector<int>map[][]이런 형태의 자료형으로 바꾸었다.
그리고 나서는 봄과 여름을 같이 구현하고 가을과 겨울을 한 반복문 안에 구현하여 시간을 줄이는데 최선을 다했다.
1) 첫번째 풀때의 자료형 형태
int foodInFarm[12][12];
int planOfAddedFood[12][12];
int treeInFarm[12][12];
map<pair<int, int>, vector<int>> treeData;
int n, m, k;2) 시간초과가 나서 바꾼 자료형 형태
int foodInFarm[12][12];
int planOfAddedFood[12][12];
vector <int> treeData[12][12];
int n, m, k;2. 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int foodInFarm[12][12];
int planOfAddedFood[12][12];
vector <int> treeData[12][12];
int n, m, k;
void foodInFarmInit()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
foodInFarm[i][j] = 5;
}
void springAndSummer(int y, int x)
{
vector<int> tmp;
sort(begin(treeData[y][x]), end(treeData[y][x]));
int dieTree = 0;
for (int i = 0; i < (int)treeData[y][x].size(); i++)
{
//봄
int treeYear = treeData[y][x][i];
if (foodInFarm[y][x] >= treeYear)
{
foodInFarm[y][x] -= treeYear;
tmp.push_back(treeYear + 1);
}
//여름
else
{
dieTree += (treeYear / 2);
}
}
treeData[y][x].clear();
treeData[y][x] = move(tmp);
foodInFarm[y][x] += dieTree;
}
/*
-- -0 -+
0- 00 0+
+- +0 ++
*/
int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dx[] = { -1, 0, 1, -1, 1,-1, 0, 1 };
void fall(int y, int x)
{
for (int i = 0; i < 8; i++)
{
int fy = y + dy[i];
int fx = x + dx[i];
if(fy >=1 && fx >=1 && fy<=n && fx<=n)
treeData[fy][fx].push_back(1);
}
}
void winter(int y, int x)
{
foodInFarm[y][x] += planOfAddedFood[y][x];
}
void oneYear()
{
//spring and summer
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (treeData[i][j].size() == 0)
continue;
//봄 여름ㄱㄱ
springAndSummer(i, j);
}
}
//fall and winter
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (treeData[i][j].size() != 0)
{
for (int k = 0; k < (int)treeData[i][j].size(); k++)
{
if (treeData[i][j][k] % 5 == 0)
{
fall(i, j);
}
}
}
//winter
winter(i, j);
}
}
}
int countTree()
{
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cnt += treeData[i][j].size();
return cnt;
}
int main()
{
cin >> n >> m >> k;
foodInFarmInit();
int value;
for(int i =1; i<=n; i++)
for (int j = 1; j <= n; j++)
{
cin >> value;
planOfAddedFood[i][j] = value;
}
int y, x, z;
for (int i = 0; i < m; i++)
{
cin >> y >>x >> z;
treeData[y][x].push_back(z);
}
//봄, 여름, 가을, 겨울
for(int i=0; i<k; i++ )
{
oneYear();
}
//살아남은 tree수
cout << countTree();
return 0;
}3. 후기
이 문제 전까지의 구현문제들은 시간에 많은 구애를 받지 않아서 시간복잡도가 빠르게 구현하기보다는 알아보기 쉽게, 고치기 쉽게 구현해왔다.
그런데 이 문제는 시간까지 생각해야하니까 구현난이도는 저번문제보다 훨씬 쉬웠지만 나에게는 오히려 더 까다로운 문제였다. 거기다가 찾기힘든 사소한 실수까지 겹치는 바람에 나무공포증이 생길뻔한 문제였다. ㅠ