글 읽기 - 반례를 못찾겠습니다! ㅠㅠ 도와주십시오

klpor0124 5년 전 0

16235 나무제태크 문제에서 반례를 못찾겠습니다.

%도 안올라가고 그냥 틀립니다.

백준테스트케이스와 질문에서 나온 1000년짜리 테스트케이스도 해봤는데..

어디가 틀렸는지 살짝 보이시는 분이나.. 반례하나 던져주실분 있나요?

감사합니다 ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, M, K;
	static final int MAX_OLD = 1011;
	static int[][] A;
	static int[][] curA;
	static int[][][] tree;
	static int[] subtree;
	static int[] dx = { 1, 1, 0, -1, -1, -1, 0, 1 };
	static int[] dy = { 0, 1, 1, 1, 0, -1, -1, -1 };	// 8방향 탐색

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int total = 0;
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		A = new int[N + 1][N + 1];		// 입력에 주어진 양분

		tree = new int[N + 1][N + 1][MAX_OLD];	// 각각의 땅마다 나이에 따른 나무 개수 
		curA = new int[N + 1][N + 1];	// 땅마다 현재 양분의 양

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
				curA[i][j] = 5;
			}
		}

		int r, c, old;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			old = Integer.parseInt(st.nextToken());
			tree[r][c][old]++;
			tree[r][c][0]++;			// r,c에 있는 전체 나무의 수
		}
		for (int i = 0; i < K; i++) {
			SpringSummer();					//봄 - 여름을 묶어서 처리 
			Fall();
			Winter();
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				total += tree[i][j][0];		//남아 있는 나무의 수
			}
		}

		System.out.println(total);

	}

	public static void SpringSummer() {

		int cnt;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				subtree = new int[MAX_OLD];			// 양분을 먹고 나이가 +1되는 나무 수를 세어 보관
				for (int k = 1, size = tree[i][j][0]; size > 0; k++) {
					cnt = 0;
					if (tree[i][j][k] != 0) {
						while (tree[i][j][k] != 0 && curA[i][j] >= k) {
							tree[i][j][k]--;			// 나이가 k인 나무의수가 0이 아니고 현재 양분이 k 보다 많으
							subtree[k + 1]++;		// 나무 수를 줄이고 나이를 +1 하여 subtree배열에 보관 
							curA[i][j] -= k;			// 양분 k만큼 -;
							cnt++;					// 현재 처리된 나무 수
						}
						size -= cnt;			// 전체 나무의 수에서 현재까지 처리된 나무의 수를 빼줌
						if (size == 0) {
							subtreeTotree(i, j);	// 양분먹고 나이가 +된 나무들을 원래 tree로 업데이트
							break;
						}
						if (curA[i][j] < k) {	    // 현재 양분이 k(나이)보다 작아지면 k이후의 나무들을 모두 /2해서 양분으로 만듦
							while (size != 0) {
								if (tree[i][j][k] != 0) {
									curA[i][j] += (k / 2) * tree[i][j][k];
								}

								tree[i][j][0] -= tree[i][j][k];
								size -= tree[i][j][k];
								tree[i][j][k] = 0;
								k++;
							}
							subtreeTotree(i, j);	
							break;
						}

					}

				}
			}
		}
	}

	public static void Fall() {
		int bCnt;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				bCnt = 0;
				for (int k = 5; k <= MAX_OLD; k += 5) {		//가을이 되면 5의배수 주변 씨뿌림
					if(tree[i][j][k] == 0) {
						bCnt += tree[i][j][k+5];				// 0이 나왔을때 나이가 최대 10차이가 나는 나무가 있을 수 있으므로 
						bCnt += tree[i][j][k+10];			// 번식 수에 더해줌
						break;
					}else {
						bCnt += tree[i][j][k];				// 0이 아니면 0이 나올때까지 더해줌
					}
				}
				treeTotree(i, j, bCnt);						// bCnt만큼 주변 8방향으로 씨뿌리는 함수
			}
		}
	}
	public static void treeTotree(int y, int x, int cnt) {

		int cy, cx;
		for (int i = 0; i < 8; i++) {
			cy = y + dy[i];
			cx = x + dx[i];

			if (isRanged(cy, cx)) {
				tree[cy][cx][1] += cnt;				// 나이가 1인 나무 수 증가시키고
				tree[cy][cx][0] += cnt;				// 전체 나무 수도 증가시킴
			}
		}
	}

	public static boolean isRanged(int y, int x) {	// map 범위 검사
		if (y >= 1 && y <= N && x >= 1 && x <= N) {
			return true;
		}
		return false;
	}

	public static void Winter() {				// 겨울되면 양분 업데이트

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				curA[i][j] += A[i][j];
			}
		}

	}

	public static void subtreeTotree(int y, int x) {
		for (int l = 1, subsize = tree[y][x][0]; subsize > 0; l++) {
			if (subtree[l] != 0) {
				tree[y][x][l] += subtree[l];
				subsize -= subtree[l];
			}
		}
	}

}

klpor0124 5년 전 2

반례 찾았습니다 ㅠㅠ

10 1 1000

100 100 100 100 100 100 100 100 100 100

1 1 1

출력은 5443이 되어야 합니다

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

문제

문제

출처

ICPC

반례를 못찾겠습니다! ㅠㅠ 도와주십시오

klpor0124 5년 전 0

klpor0124 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말