글 읽기 - 마지막 예시에서 85가 아니라 86이 나옵니다...

cleankid99 5년 전 0

안에 코드에 주석은 다 적어놓았어요

왜 1이 더 크게 나오는지 모르겠어요....

한번 디버깅 같이 해주실 수 있으실까요..??

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <utility>
using namespace std;

// 나무가 번식할때 
const int dy[] = {-1,-1,-1,0,0,1,1,1};
const int dx[] = {-1,0,1,-1,1,-1,0,1};

vector<int> z[11][11]; // 삼중배열
queue<pair<int, int> > q; // 추가 나무
int map[11][11]; // 현재양분
int A[11][11]; // 받아오는 양분
int tree[11][11]; // 나무 수
int ttemp[11][11]; // 증가되는 나무 수
int n, m, k, year;

int main() {
	cin >> n >> m >> k;
	
	// 5로 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			map[i][j]=5;
		}
	}
	// 양분 받아옴(매년 더해주기)
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, age;
		cin >> x >> y >> age; // (x,y) 위치에 나무가 몇개있는지 알 수 없음, 따라서 벡터로 구현하여 추가
		z[x][y].push_back(age);
		tree[x][y]++;
	}

	


	for (year = 0; year < k; year++) {
		//봄, 여름
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (tree[i][j] != 0) { // 나무가 있으면
					//int size = z[i][j].size(); // 나무의 수
					sort(z[i][j].begin(), z[i][j].end()); // 나무의 나이가 어린 순으로 정렬
					for (int l = 0; l < z[i][j].size(); l++) {
						if (map[i][j] >= z[i][j][l]) { // 양분이 나무의 나이 이상이면
							map[i][j] -= z[i][j][l]; // 양분 감소
							z[i][j][l]++; // 나이 증가							
						}
						else { // 아니라면 나무 죽음
							map[i][j] = map[i][j] + z[i][j][l] / 2;
							z[i][j][l] = 11;//죽었단 소리.
							tree[i][j]--;
							sort(z[i][j].begin(), z[i][j].end());// 다시 어린순으로 정렬 
							z[i][j].pop_back(); // 마지막 11(죽은거) pop
						}
					}
				}
			}
		}
		//가을
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (tree[i][j] != 0) { // 나무가 있으면
					//int size = z[i][j].size(); // 나무의 수
					for (int l = 0; l < z[i][j].size(); l++) {
						if (z[i][j][l] % 5 == 0) { // 나무의 나이가 5의 배수일 경우
							for (int p = 0; p < 8; p++) {
								int nx = i + dx[p], ny = j + dy[p];
								if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
									ttemp[nx][ny]++; // 나무 번식
									q.push(make_pair(nx, ny)); // 나무 추가
									//z[nx][ny].push_back(1); 
								}
							}

						}

					}

				}

			}
		}

		while (!q.empty()) { // 나무 추가
			int i = q.front().first, j = q.front().second;
			q.pop();
			z[i][j].push_back(1);
		}

		

		//겨울
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				map[i][j] += A[i][j]; // 양분 추가
				tree[i][j] += ttemp[i][j]; // 나무 수 증가
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				ttemp[i][j] = 0; // 생성된 나무 초기화
			}
		}
		

	}

	// 출력
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (tree[i][j] != 0) {
				sum += tree[i][j];
			}
		}
	}

	cout << sum << '\n';

	return 0;
}

seico75 5년 전 3

53 라인 루프 안에서 3가지 문제가 있는 것 같습니다.

1번째.

63라인에서 pop_back를 하는데, 전체가 길이가 5 이고, l = 2 이면... 1, 2, 3, 4, 5 를 가진다고 하면

1, 2, 11, 4, 5 가 되고 1, 2, 4, 5, 11 이 된 후 pop_back 해서 1, 2, 4, 5 가 남습니다.

for 루프가 다시 시작되면 이제 길이는 4가 되고 l은 하나 증가 3이 되어서 '5'를 가리킵니다.

즉, '4'에 대해서는 처리가 skip 됩니다.

2번째.

1, 2, 4, 5, 6 의 나무가 있을 때 양분은 6이라고 가정을 하면

1, 2는 양분이 있으니 l=2으로 for 진입하면

2, 3, 4, 5, 6 이 되고 양분은 3이 남죠. 4는 죽으면서 2의 양분을 남기면

5에 대해서 처리할 때 (1번째 경우를 해결했다고 하면..) 양분은 5가 된 상태여서 5인 나무가 안죽고 양분을 먹게 됩니다.

이것은 문제에서 의도한 바가 아니기 때문에 한번 나무들이 죽기 시작하면 뒤는 다 죽이거나

봄과 여름을 분리하거나 해야할 것 같습니다.

3번째

죽은 나무를 11이라고 했는데, 나무나이가 11보다 작다는 가정을 할 수 없을 것 같습니다.

결론은...

나무가 죽기 시작하면 loop 빠져나가서 다 죽이고, pop_back 하면서 양분을 만들어 버리는 것이 어떨까요?

그리고 정답을 맞추고 나시면 다른 분을 코드를 꼭 한번 보세요.

cleankid99 5년 전 0

댓글 달아주셔서 감사합니다!!

저도 계속 코드를 리뷰하면서 보니

그런 문제가 있어서

아예 수정을 해봤는데

이제는 마지막 예제의 답이 91이 나오더라구요..

근데 제가 직접 손으로 다 일일이 해봤는데 똑같이 91이 나오던데

어떻게 85가 나오게 된건지 모르겠어요,,,ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 나무가 번식할때 
const int dy[] = {-1,-1,-1,0,0,1,1,1};
const int dx[] = {-1,0,1,-1,1,-1,0,1};

vector<int> tree[11][11]; // 삼중배열
int map[11][11]; // 현재양분
int A[11][11]; // 받아오는 양분
vector<int> dead; // 죽은 나무 index 저장
int n, m, k, year;

int main() {
	cin >> n >> m >> k;
	
	// 5로 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> A[i][j];
			map[i][j]=5;
			tree[i][j].clear();
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, age;
		cin >> x >> y >> age; // (x,y) 위치에 나무가 몇개있는지 알 수 없음, 따라서 벡터로 구현하여 추가
		x--;
		y--;
		tree[y][x].push_back(age);
	}

	


	for (year = 0; year < k; year++) {
		//봄 & 여름
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int size = tree[i][j].size();
				dead.clear();
				for (int l = 0; l < size; l++) {
					if (map[i][j] >= tree[i][j][l]) { // 양분이 나무의 나이 이상이면
						map[i][j] -= tree[i][j][l]; // 양분 감소
						tree[i][j][l]++; // 나이 증가							
					}
					else { // 아니라면 나무 죽음
						map[i][j] += tree[i][j][l] / 2;
						dead.push_back(l); // 죽어야하는 나무 인덱스 저장
					}
				}
				for (int l = 0; l < dead.size(); l++) { // tree[i][j]의 죽은 나무 처리
					int x = dead[l]; // 죽을 나무 인덱스
					tree[i][j][x] = 11;
					sort(tree[i][j].begin(), tree[i][j].end());
					tree[i][j].pop_back();
				}
			}
		}
		
		//가을
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int size = tree[i][j].size();								
				for (int l = 0; l < size; l++) {
					if (tree[i][j][l] % 5 == 0) { // 나무의 나이가 5의 배수일 경우
						for (int p = 0; p < 8; p++) {
							int nx = i + dx[p], ny = j + dy[p];
							if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
								tree[nx][ny].push_back(1);
							}
						}

					}
				}	

			}
		}		

		//겨울
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				sort(tree[i][j].begin(), tree[i][j].end());
				map[i][j] += A[i][j]; // 양분 추가
			}
		}

		/*int size = dead.size();
		for (int i = 0; i < size; i++) {
			dead.pop_back();
		}*/
		dead.clear(); // 초기화
	}

	// 출력
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sum += tree[i][j].size();
		}
	}

	cout << sum << '\n';

	return 0;
}

seico75 5년 전 1

제가 위에 남긴 글의 2번째 부분이 아직도 해결이 안되어 있습니다.

그리고, 29 번째 라인이 x, y가 맞는지 y, x 가 맞는지 확인해보셔야 할 것 같습니다.

이문제에 x,y r,c가 좀 헷갈리게 써 있어서요

cleankid99 5년 전 0

아....

한번 나무가 죽기 시작하면 다죽어야하는군요...

으아아아아아아아악

감사합니다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

마지막 예시에서 85가 아니라 86이 나옵니다...

cleankid99 5년 전 0

seico75 5년 전 3

cleankid99 5년 전 0

seico75 5년 전 1

cleankid99 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말