본문 바로가기
code/BOJ

백준 16235 나무 재테크

장동욱 2019. 10. 9. 17:53

문제:

 

16235번: 나무 재테크

부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든

www.acmicpc.net

설계:

스케쥴러 유형에서 자주 사용하는 list를 사용하려 했으나 결과는 런타임 에러, 시간초과

multiset 역시 시간 초과

 

deque로 구현, 76ms 소요:

/* 1. 좌표 1부터 시작 */
/* 2. 봄 작업은 nt에 의존, 여름은 nt 수정 => 둘이 동시에 수행하면 x */

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int T;
int N, M, K;
int A[12][12], nt[12][12];
deque<int> tr[12][12];

const int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

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

	cin >> N >> M >> K;				// part 1 

	for (int r = 1; r < N + 1; ++r) {	// part 2 양분
		for (int c = 1; c < N + 1; ++c) {
			cin >> A[r][c];
		}
	}

	for (int r = 1; r < N + 1; ++r)
		fill(nt[r] + 1, nt[r] + N + 1, 5);

	while (M--) {					// part 3 나무
		int x, y, z;
		cin >> x >> y >> z;
		tr[x][y].push_back(z);	/* 1 */
	}

	for (int r = 1; r < N + 1; ++r) {
		for (int c = 1; c < N + 1; ++c) {
			sort(tr[r][c].begin(), tr[r][c].end());
		}
	}
	
	for (int k = 0; k < K; ++k) {
		// 봄
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				int dd = 0;
				int rep = tr[r][c].size();
				while (rep--) {
					if (nt[r][c] >= tr[r][c].front()) {
						nt[r][c] -= tr[r][c].front();				// 먹은 만큼 양분 감소
						tr[r][c].push_back(tr[r][c].front() + 1);
						tr[r][c].pop_front();
					}
					else {
						dd += tr[r][c].front() / 2;
						tr[r][c].pop_front();
					}
				}
				nt[r][c] += dd;
			}
		}

		// 가을
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				for (auto t : tr[r][c]) {
					if (t % 5 == 0) {
						for (int d = 0; d < 8; ++d) {
							tr[r + dr[d]][c + dc[d]].push_front(1);
						}
					}
				}
			}
		}

		// 겨울
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				nt[r][c] += A[r][c];
			}
		}
	}
		
	int ans = 0;
	for (int r = 1; r < N + 1; ++r) {
		for (int c = 1; c < N + 1; ++c) {
			ans += tr[r][c].size();
		}
	}
	
	cout << ans;
	
	return 0;
}

vector로 구현, 124ms 소요

/* 1. 좌표 1부터 시작 */
/* 2. 봄 작업은 nt에 의존, 여름은 nt 수정 => 둘이 동시에 수행하면 x */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T;
int N, M, K;
int A[12][12], nt[12][12];
vector<int> tr[12][12];
vector<int> tmp;

#define IN(r, c) (0 <= (r) && (r) < N && 0 <= (c) && (c) < N)
const int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

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

	cin >> N >> M >> K;				// part 1 

	for (int r = 1; r < N + 1; ++r) {	// part 2 양분
		for (int c = 1; c < N + 1; ++c) {
			cin >> A[r][c];
		}
	}

	for (int r = 1; r < N + 1; ++r)
		fill(nt[r] + 1, nt[r] + N + 1, 5);

	while (M--) {					// part 3 나무
		int x, y, z;
		cin >> x >> y >> z;
		tr[x][y].push_back(z);	/* 1 */
	}

	for (int k = 0; k < K; ++k) {
		// 봄
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				if (!tr[r][c].size()) continue;
				sort(tr[r][c].begin(), tr[r][c].end());

				tmp.clear();
				int dd = 0;
				for (auto t : tr[r][c]) {
					if (nt[r][c] >= t) {
						nt[r][c] -= t;				// 먹은 만큼 양분 감소
						tmp.push_back(t + 1);
					}
					else {
						dd += t / 2;
					}
				}
				nt[r][c] += dd;
				tr[r][c] = tmp;
			}
		}

		// 가을
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				for (auto t : tr[r][c]) {
					if (t % 5 == 0) {
						for (int d = 0; d < 8; ++d) {
							tr[r + dr[d]][c + dc[d]].push_back(1);
						}
					}
				}
			}
		}

		// 겨울
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				nt[r][c] += A[r][c];
			}
		}
	}
		
	int ans = 0;
	for (int r = 1; r < N + 1; ++r) {
		for (int c = 1; c < N + 1; ++c) {
			ans += tr[r][c].size();
		}
	}
	
	cout << ans;
	
	return 0;
}

multiset으로 구현, 시간 초과

/* 1. 좌표 1부터 시작 */
/* 2. 봄 작업은 nt에 의존, 여름은 nt 수정 => 둘이 동시에 수행하면 x */

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int T;
int N, M, K;
int A[12][12], nt[12][12];
multiset<int> tr[12][12];
multiset<int> tmp;

const int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

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

	cin >> N >> M >> K;				// part 1 

	for (int r = 1; r < N + 1; ++r) {	// part 2 양분
		for (int c = 1; c < N + 1; ++c) {
			cin >> A[r][c];
		}
	}

	for (int r = 1; r < N + 1; ++r)
		fill(nt[r] + 1, nt[r] + N + 1, 5);

	while (M--) {					// part 3 나무
		int x, y, z;
		cin >> x >> y >> z;
		tr[x][y].insert(z);	/* 1 */
	}
	
	for (int k = 0; k < K; ++k) {
		// 봄
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				if (!tr[r][c].size()) continue;
				tmp.clear();
				int dd = 0;
				for (auto it = tr[r][c].begin(); it != tr[r][c].end();) {
					if (nt[r][c] >= *it) {
						nt[r][c] -= *it;				// 먹은 만큼 양분 감소
						tmp.insert(*it + 1);
						++it;
					}
					else {
						dd += (*it) / 2;
						tr[r][c].erase(it++);
					}
				}
				tr[r][c] = tmp;
				nt[r][c] += dd;
			}
		}

		// 가을
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				for (auto t : tr[r][c]) {
					if (t % 5 == 0) {
						for (int d = 0; d < 8; ++d) {
							tr[r + dr[d]][c + dc[d]].insert(1);
						}
					}
				}
			}
		}

		// 겨울
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				nt[r][c] += A[r][c];
			}
		}
	}
		
	int ans = 0;
	for (int r = 1; r < N + 1; ++r) {
		for (int c = 1; c < N + 1; ++c) {
			ans += tr[r][c].size();
		}
	}
	
	cout << ans;
	
	return 0;
}

list로 구현, 시간 초과

/* 1. 좌표 1부터 시작 */
/* 2. 봄 작업은 nt에 의존, 여름은 nt 수정 => 둘이 동시에 수행하면 x */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T;
int N, M, K;
int A[12][12], nt[12][12];
vector<int> tr[12][12];
vector<int> tmp;

#define IN(r, c) (0 <= (r) && (r) < N && 0 <= (c) && (c) < N)
const int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

struct dd {
	int r, c, n;
};
vector<dd> dtr;

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

	cin >> N >> M >> K;				// part 1 

	for (int r = 1; r < N + 1; ++r) {	// part 2 양분
		for (int c = 1; c < N + 1; ++c) {
			cin >> A[r][c];
		}
	}

	for (int r = 1; r < N + 1; ++r)
		fill(nt[r] + 1, nt[r] + N + 1, 5);

	while (M--) {					// part 3 나무
		int x, y, z;
		cin >> x >> y >> z;
		tr[x][y].push_back(z);	/* 1 */
	}

	for (int k = 0; k < K; ++k) {
		// 봄
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				tmp.clear();
				for(auto t : tr[r][c]){
					if (nt[r][c] >= t) {
						nt[r][c] -= t;				// 먹은 만큼 양분 감소
						tmp.push_back(t + 1);
					}
					else {
						dtr.push_back({ r, c, t / 2 });
					}
				}
				tr[r][c] = tmp;
			}
		}

		// 여름
		for (auto d : dtr) {
			nt[d.r][d.c] += d.n;
		}

		// 가을
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				for (auto t : tr[r][c]) {
					if (t % 5 == 0) {
						for (int d = 0; d < 8; ++d) {
							tr[r + dr[d]][c + dc[d]].push_back(1);
						}
					}
				}
			}
		}

		// 겨울
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				nt[r][c] += A[r][c];
			}
		}

		int ans = 0;
		for (int r = 1; r < N + 1; ++r) {
			for (int c = 1; c < N + 1; ++c) {
				ans += tr[r][c].size();
			}
		}
	}

	int ans = 0;
	for (int r = 1; r < N + 1; ++r) {
		for (int c = 1; c < N + 1; ++c) {
			ans += tr[r][c].size();
		}
	}

	cout << ans;
	return 0;
}
저작자표시 비영리 변경금지

'code/BOJ' Related Articles

티스토리툴바