글 읽기 - 반례부탁드립니다

ehgus607 4년 전 0

덱으로 구현하였습니다.

문제에서 제시하는 테스트케이스는 다 통과됩니다.

고수님들의 조언 부탁드리겠습니다.

#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;

typedef struct Tree {
	int age;
	int dead;
};
typedef struct Map {
	deque<Tree> tree;
	int nutrient = 5;
	int A = 0;
};

Map map[11][11];
int dx[8] = { 0,-1,-1,-1,0,1,1,1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int N, M, K;

void spring() {
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int size = map[r][c].tree.size();
			for (int t = 0; t < size; t++) {
				int age = map[r][c].tree.front().age;
				map[r][c].tree.pop_front();

				if (age <= map[r][c].nutrient)
				{
					map[r][c].nutrient -= age;
					map[r][c].tree.push_back({ age+1, 0 });
				}
				else {
					map[r][c].tree.push_back({ age, 1 });
				}
			}
		}
	}
}
void summer() {
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int size = map[r][c].tree.size();
			for (int t = 0; t < size; t++) {
				int age = map[r][c].tree.front().age;
				int dead = map[r][c].tree.front().dead;
			
				if (dead == 1)
				{
					map[r][c].nutrient += (age / 2);
					map[r][c].tree.pop_front();
				}
				else {
					map[r][c].tree.push_back(map[r][c].tree.front());
					map[r][c].tree.pop_front();
				}
			}
		}
	}
}

void fall() {
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int size = map[r][c].tree.size();
			for (int t = 0; t < size; t++) {
				int age = map[r][c].tree.front().age;
				map[r][c].tree.pop_front();

				if (age % 5 == 0) {
					for (int d = 0; d < 8; d++) {
						int nr = r + dy[d];
						int nc = c + dx[d];
						if (nr >= 1 && nr <= N && nc >= 1 && nc <= N) {
							map[nr][nc].tree.push_front({ 1,0 });
						}
					}
				}
				map[r][c].tree.push_back({ age, 0 });
			}
		}
	}
}
void winter() {
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			map[r][c].nutrient += map[r][c].A;
		}
	}
}

bool cmp(Tree a, Tree b) {
	return a.age < b.age;
}

int main() {
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			scanf("%d", &map[r][c].A);
		}
	}
	for (int i = 0; i < M; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);

		map[y][x].tree.push_front({z, 0});
	}
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			sort(map[r][c].tree.begin(), map[r][c].tree.end(), cmp);
		}
	}
	

	for (int k = 0; k < K; k++) {
		spring();
		summer();
		fall();
		winter();
	}
	int res = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			res += map[r][c].tree.size();
		}
	}
	printf("%d\n", res);
}

seico75 4년 전 1

문제 기술이 많이 헷갈리는데,

(r, c) 로되어 있고, (x, y) 로 되어 있기 때문에 r == x, c == y 입니다.

107이나 109라인을 고치면 되겠네요.

그리고, 사족으로 deque 에서 꺼냈다가 넣었다가 하지 않고 그냥 업데이트 하시는 것도 가능할 것 같습니다.

ehgus607 4년 전 0

아하! 그렇군요

좋은 답변 감사드립니다.

지적해주신것도 한번 시도해보겠습니다. ㅎㅎ

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

문제

문제

출처

ICPC

반례부탁드립니다

ehgus607 4년 전 0

seico75 4년 전 1

ehgus607 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말