글 읽기 - 반례는 찾았는데 이유를 모르겠습니다 ㅠㅠ

jadekwon 4년 전 0

10
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
0 0 64 32 32 0 0 0 0 0
0 32 32 64 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0
64 64 128 0 0 0 0 0 0 0
128 32 2 4 0 0 0 0 0 0
0 0 128 0 0 0 0 0 0 0

답 : 1024

output: 256

위 반례를 찾았는데.. 왜 안되는지 이유를 모르겠어요 ㅠㅠ

재귀로 4방향 다 돌렸구요

값이 같으면 더한 후 바로 다음칸부터 다시 숫자를 비교해서 중복되게 더해지진 않는 것 같아요.

며칠째 이것만 파고있네요.. 도움주시면 정말 감사합니다 ㅠㅠ

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

public class P12100 {
	static int N;
	static int max;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		max = 0;
		N = Integer.parseInt(br.readLine());
		
		int[][] map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		move(0, map);
		
		bw.write(max + "");
		
		bw.flush();
		br.close();
		bw.close();
	}
	
	// 네 방향 이동
	public static void move(int count, int map[][]) {
//		System.out.println(count);
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.print(map[i][j] + " ");
//			}
//			System.out.println();
//		}
		
		if (count == 5) {
			// 가장 큰 값 저장
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (max < map[i][j]) max = map[i][j];
				}
			}
			
			return;
		}
		
		System.out.println("up");
		move(count + 1, up(map));
		
		System.out.println("down");
		move(count + 1, down(map));
		
		System.out.println("left");
		move(count + 1, left(map));
		
		System.out.println("right");
		move(count + 1, right(map));
	}
	
	public static int[][] up(int[][] map) {
		// 상
		boolean isChanged = false;
		for (int x = 0; x < N; ++x) {
			int y = 0;
			while (y < N - 1) {
				if (map[y][x] == 0) {
					++y;
					isChanged = true;
					continue;
				}
				
				int nextY = y;
				while (++nextY < N) {
					if (map[nextY][x] == 0) continue;
					
					if (map[y][x] == map[nextY][x]) {
						map[y][x] *= 2;
						map[nextY][x] = 0;
						y = nextY + 1;
						isChanged = true;
					}
					else {
						y = nextY;
					}
					
					break; 
				}
				
				if (nextY > N - 1) break;
			}
		}
		
		if (isChanged) {
			// 이동
			for (int x = 0; x < N; ++x) {
				int spaceY = -1;
				for (int y = 0; y < N; ++y) {
					if (map[y][x] == 0) {
						if (spaceY == -1) spaceY = y;
					}
					else {
						if (spaceY != -1) {
							map[spaceY][x] = map[y][x];
							map[y][x] = 0;
							if (y - spaceY > 1) ++spaceY;
							else spaceY = y;
						}
					}
				}
			}
		}
		
		return map;
	}

	public static int[][] down(int[][] map) {
		// 하
		boolean isChanged = false;
		for (int x = 0; x < N; ++x) {
			int y = N - 1;
			while (y > 0) {
				if (map[y][x] == 0) {
					--y;
					isChanged = true;
					continue;
				}
				
				int nextY = y;
				while (--nextY >= 0) {
					if (map[nextY][x] == 0) continue;
					
					if (map[y][x] == map[nextY][x]) {
						map[y][x] *= 2;
						map[nextY][x] = 0;
						y = nextY - 1;
						isChanged = true;
					}
					else {
						y = nextY;
					}
					
					break;
				}

				if (nextY <= 0) break;
			}
		}

		if (isChanged) {
			// 이동
			for (int x = 0; x < N; ++x) {
				int spaceY = -1;
				for (int y = N - 1; y >= 0; --y) {
					if (map[y][x] == 0) {
						if (spaceY == -1) spaceY = y;
					}
					else {
						if (spaceY != -1) {
							map[spaceY][x] = map[y][x];
							map[y][x] = 0;

							if (spaceY - y > 1) --spaceY;
							else spaceY = y;
						}
					}
				}
			}
		}
		
		return map;
	}

	public static int[][] left(int[][] map) {
		// 좌
		boolean isChanged = false;
		for (int y = 0; y < N; ++y) {
			int x = 0;
			while (x < N - 1) {
				if (map[y][x] == 0) {
					++x;
					isChanged = true;
					continue;
				}
				
				int nextX = x;
				while (++nextX < N) {
					if (map[y][nextX] == 0) continue;
					
					if (map[y][x] == map[y][nextX]) {
						map[y][x] *= 2;
						map[y][nextX] = 0;
						x = nextX + 1;
						isChanged = true;
					}
					else {
						x = nextX;
					}
					
					break;
				}

				if (nextX > N - 1) break;
			}
		}

		if (isChanged) {
			// 이동
			for (int y = 0; y < N; ++y) {
				int spaceX = -1;
				for (int x = 0; x < N; ++x) {
					if (map[y][x] == 0) {
						if (spaceX == -1) spaceX = x;
					}
					else {
						if (spaceX != -1) {
							map[y][spaceX] = map[y][x];
							map[y][x] = 0;
							
							if (x - spaceX > 1) ++spaceX;
							else spaceX = x;
						}
					}
				}
			}
		}
		
		return map;
	}

	public static int[][] right(int[][] map) {
		// 우
		boolean isChanged = false;
		for (int y = 0; y < N; ++y) {
			int x = N - 1;
			while (x > 0) {
				if (map[y][x] == 0) {
					--x;
					isChanged = true;
					continue;
				}
				
				int nextX = x;
				while (--nextX >= 0) {
					if (map[y][nextX] == 0) continue;
					
					if (map[y][x] == map[y][nextX]) {
						map[y][x] *= 2;
						map[y][nextX] = 0;
						x = nextX - 1;
						isChanged = true;
					}
					else {
						x = nextX;
					}
					
					break;
				}

				if (nextX <= 0) break;
			}
		}


		if (isChanged) {
			// 이동
			for (int y = 0; y < N; ++y) {
				int spaceX = -1;
				for (int x = N - 1; x >= 0; --x) {
					if (map[y][x] == 0) {
						if (spaceX == -1) spaceX = x;
					}
					else {
						if (spaceX != -1) {
							map[y][spaceX] = map[y][x];
							map[y][x] = 0;

							if (spaceX - x > 1) --spaceX;
							else spaceX = x;
						}
					}
				}
			}
		}
		
		return map;
	}
}

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

문제

문제

출처

ICPC

반례는 찾았는데 이유를 모르겠습니다 ㅠㅠ

jadekwon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말