백준 16235번 : 나무 재테크 시간 초과 해결 C++

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

1.문제설명

 

봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.

 

여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.

가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다.

 

겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.

 

문제에서 설명한 단계에 맞춰서 똑같이 구현하면 됩니다.

 

---

2.접근방법[알고리즘]

구현과 동시에 코드 최적화가 핵심입니다.

시간제한이 0.3초여서 최대한 최적화해야 해결할 수 있습니다.

 

이 문제에서 한 칸 안에 나무 여러 개가 있을 수 있습니다.

한 칸에 나무가 여러 개 있을 경우 나이가 적은 나무 부터 양분을 섭취해야합니다.

 

이때 자연스럽게 매번마다 나무를 오름차순으로 sort한 뒤 양분을 섭취하게끔 해야겠다는 생각이 듭니다.

하지만 그러면 시간초과로 틀립니다.

 

문제 조건 상 sort는 맨 처음 한 번만 해도 풀 수 있습니다.

 

8칸에 새로 생기는 나무의 나이는 무조건 1이기 때문에

새로 생긴 나무를 맨 앞으로 보내주고

이전에 있던 나무들은 뒤로 보내주면 sort를 해주지 않아도 됩니다.

 

---

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, k, ans, arr[11][11], added[11][11];
int dx[8] = { 1,0,-1,0,1,-1,1,-1 };
int dy[8] = { 0,1,0,-1,1,-1,-1,1 };

struct Tree {
	int x, y, age;
	bool operator<(const Tree &bb) const {
		return age < bb.age;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	vector<Tree> v;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> added[i][j];
			arr[i][j] = 5;
		}
	}

	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v.push_back({ x,y,z });
	}

	sort(v.begin(), v.end());
	
	for (int K = 0; K < k; K++) {
		vector<Tree> new_v;

		// 봄
		for (int i = 0; i < v.size(); i++) {
			if (v[i].age == 0) continue;

			if (v[i].age <= arr[v[i].x][v[i].y]) {
				arr[v[i].x][v[i].y] -= v[i].age;
				v[i].age++;

				// 가을에 새로 생기는 나무들
				if (v[i].age % 5 == 0) {
					for (int j = 0; j < 8; j++) {
						int nx = v[i].x + dx[j];
						int ny = v[i].y + dy[j];
                        
						//new_v 벡터에 새로생기는 나무들 먼저 넣어줌
						if (nx <= 0 || nx > n || ny <= 0 || ny > n)continue;
						new_v.push_back({ nx, ny, 1 });
					}
				}
			}
			else {
            	//죽은 나무들 
				v[i].age = -v[i].age;
			}
		}

		//여름 
		for (int i = 0; i < v.size(); i++) {
        //죽은 나무들 양분으로 전환 
			if (v[i].age < 0)
			{
				arr[v[i].x][v[i].y] += (-v[i].age / 2);
			}
			else {
            //new_v에 기존에 있던 나무들 뒤로 보내줌 
				new_v.push_back(v[i]);
			}
		}

		// 겨울
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				arr[i][j] += added[i][j];
			}
		}

		v.swap(new_v);
	}


	cout << v.size() << '\n';
	return 0;
	
}

백준 16235번 시간초과 해결

 

 

 

백준 16235번: 나무 재테크 반례

이 테스트케이스가 오래 걸린다면 통과할 수 없습니다.

10 100 1000
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
1 1 4
1 2 4
1 3 4
1 4 4
1 5 4
1 6 4
1 7 4
1 8 4
1 9 4
1 10 4
2 1 4
2 2 4
2 3 4
2 4 4
2 5 4
2 6 4
2 7 4
2 8 4
2 9 4
2 10 4
3 1 4
3 2 4
3 3 4
3 4 4
3 5 4
3 6 4
3 7 4
3 8 4
3 9 4
3 10 4
4 1 4
4 2 4
4 3 4
4 4 4
4 5 4
4 6 4
4 7 4
4 8 4
4 9 4
4 10 4
5 1 4
5 2 4
5 3 4
5 4 4
5 5 4
5 6 4
5 7 4
5 8 4
5 9 4
5 10 4
6 1 4
6 2 4
6 3 4
6 4 4
6 5 4
6 6 4
6 7 4
6 8 4
6 9 4
6 10 4
7 1 4
7 2 4
7 3 4
7 4 4
7 5 4
7 6 4
7 7 4
7 8 4
7 9 4
7 10 4
8 1 4
8 2 4
8 3 4
8 4 4
8 5 4
8 6 4
8 7 4
8 8 4
8 9 4
8 10 4
9 1 4
9 2 4
9 3 4
9 4 4
9 5 4
9 6 4
9 7 4
9 8 4
9 9 4
9 10 4
10 1 4
10 2 4
10 3 4
10 4 4
10 5 4
10 6 4
10 7 4
10 8 4
10 9 4
10 10 4

답

 8456​