글 읽기 - 안녕하세요. 2873번 롤러코스터 문제에 대해 여쭙고 싶습니다.

95qwer 1년 전 0

현재
5 3
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5

2 2
2 1
2 2

2 2

1 2

4 2
3 4
5 5
2 2
1 9

4 4
3 1 8 5
5 5 5 5
5 5 5 5
5 5 5 5
4 4
1 1 1 1
1 1 1 1
1 1 1 5
1 1 1 1

4 4
1 5 1 1
1 1 1 1
1 1 1 5
1 1 1 1

4 6
4 3 5 1 5 3
4 2 4 3 4 5
3 4 5 3 4 4
8 9 3 8 5 5

6 4
3 1 8 5
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5

block row = 1
6 6
4 3 5 1 5 3
4 2 4 3 4 5
3 4 5 3 4 4
8 9 3 8 5 5
9 7 2 5 6 3
4 5 2 3 5 2

6 6
4 1 5 6 5 3
4 2 4 3 4 5
3 4 5 3 4 4
8 9 3 8 5 5
9 7 2 5 6 3
4 5 2 3 5 2

block row = 2
6 6
4 3 5 7 5 3
1 2 4 3 4 5
3 4 5 3 4 4
8 9 3 8 5 5
9 7 2 5 6 3
4 5 2 3 5 2

block row = 3
6 6
4 3 5 7 5 3
6 2 4 3 4 5
5 1 5 3 4 4
8 9 3 8 5 5
9 7 2 5 6 3
4 5 2 3 5 2

block row = 4
6 6
4 3 5 7 5 3
6 2 4 3 4 5
5 6 5 3 4 4
1 9 3 8 5 5
9 7 2 5 6 3
4 5 2 3 5 2

8 8
4 3 5 7 5 3 5 5
8 2 4 3 4 5 5 5
3 4 5 3 4 4 5 5
8 9 3 8 5 5 5 5
8 7 2 5 6 3 5 5
1 5 2 3 5 2 5 5
9 7 2 5 6 3 5 5
4 5 2 3 5 2 5 5

8 4
4 4 4 1
4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4
16 16
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 1 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5
4 3 5 7 5 3 5 5 4 3 5 7 5 3 5 5

뜽의 반례를 시도해보고 있습니다.

위의 반례 외에 뭔가 틀릴 만한 반례 없을지 궁금합니다. 코드는 너무 스파게티라서...

package test;

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

public class P2873 {
	static int[][] matrix;

	public static void main(String[] args) throws IOException {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
		PriorityQueue<Block> pq = new PriorityQueue<>();
		String mInfo = bfr.readLine();
		int row = Integer.parseInt(mInfo.split(" ")[0]);
		int col = Integer.parseInt(mInfo.split(" ")[1]);
		matrix = new int[row + 1][col + 1];
		if (row % 2 == 0 && col % 2 == 0) {
			for (int i = 1; i < row + 1; i++) {
				StringTokenizer st = new StringTokenizer(bfr.readLine(), " ");
				for (int j = 1; j < col + 1; j++) {
					int point = Integer.parseInt(st.nextToken());
					matrix[i][j] = point;
					if ((i % 2 == 0 && j % 2 != 0) || (i % 2 != 0 && j % 2 == 0)) {
						Block b = new Block(point, i, j);
						pq.add(b);
					}
				}
			}
		} else {
			for (int i = 1; i < row + 1; i++) {
				StringTokenizer st = new StringTokenizer(bfr.readLine(), " ");
				for (int j = 1; j < col + 1; j++) {
					int point = Integer.parseInt(st.nextToken());
					matrix[i][j] = point;
				}
			}
		}
		if (row % 2 != 0) {
			boolean trigger = true;
			for (int i = 0; i < row; i++) {
				if (trigger) {
					for (int j = 0; j < col - 1; j++)
						bfw.write("R");
					trigger = false;
				} else {
					for (int j = col - 1; j > 0; j--)
						bfw.write("L");
					trigger = true;
				}
				if (row != 1 && i != row - 1)
					bfw.write("D");
			}
		} else if (row % 2 == 0 && col % 2 != 0) {
			boolean trigger = true;
			for (int i = 0; i < col; i++) {
				if (trigger) {
					for (int j = 0; j < row - 1; j++)
						bfw.write("D");
					trigger = false;
				} else {
					for (int j = row - 1; j > 0; j--)
						bfw.write("U");
					trigger = true;
				}
				if (row != 1 && i != col - 1)
					bfw.write("R");
			}
		} else {
			while (true) {
				Block b = pq.poll();
				if (b.row == row && b.col == col)
					b = pq.poll();
				int blockRow = b.row;
				int blockCol = b.col;
				if (blockRow == 1) { // 블락 처리한 것이 출발지점과 같은 행에 있을 때
					int i = 1;
					int j = 1;
					while (true) {
						bfw.write("D");
						i++;
						if (j < col) {
							bfw.write("R");
							j++;
						} else
							break;
						if (i - 1 == blockRow && j == blockCol) {
							if (blockRow != row && blockCol != col) {
								bfw.write("RUR");
								i--;
								j += 2;
							} else // block처리한 곳이 사각형의 꼭지점일 때.
								break;
						} else {
							bfw.write("UR");
							i--;
							j++;
						}
					}
					if (i < row) {
						bfw.write("D");
						i++;
					}
					if (i == row && j == col)
						break;
					boolean trigger = true;

					for (; i < row + 1; i++) {
						if (trigger) {
							for (; j > 1; j--)
								bfw.write("L");
							trigger = false;
						} else {
							for (; j < col; j++)
								bfw.write("R");
							trigger = true;
						}
						if (i != row)
							bfw.write("D");
					}
					break;
				} else if (blockRow == 2) {
					int i = 1;
					int j = 1;
					while (true) {
						if (i + 1 == blockRow && j == blockCol) {
							bfw.write("RD");
							i++;
							j++;
						} else {
							bfw.write("D");
							i++;
						}
						
						if (j < col) {
							bfw.write("R");
							j++;
						} else
							break;
						bfw.write("U");
						i--;
						if (j < col) {
							bfw.write("R");
							j++;
						} else
							break;
					}
					if (i < row) {
						bfw.write("D");
						i++;
					}
					if (i == row && j == col)
						break;
					boolean trigger = true;

					for (; i < row + 1; i++) {
						if (trigger) {
							for (; j > 1; j--)
								bfw.write("L");
							trigger = false;
						} else {
							for (; j < col; j++)
								bfw.write("R");
							trigger = true;
						}
						if (i != row)
							bfw.write("D");
					}
					break;
				} else { // 이후부터는 blockRow = 1 / blockRow =2의 경우가 반복된다. 이에 맞춰 만들어주면 됨.
					int i = 1;
					int j = 1;
					if (blockRow % 2 != 0) {
						boolean trigger = false;
						for (; i < row + 1; i++) {
							if (i == blockRow) {
								while (true) {
									bfw.write("D");
									i++;
									if (j < row) {
										bfw.write("R");
										j++;
									} else
										break;
									if (i - 1 == blockRow && j == blockCol) {
										if (blockRow != row && blockCol != col) {
											bfw.write("RUR");
											i--;
											j += 2;
										} else // block처리한 곳이 사각형의 꼭지점일 때.
											break;
									} else {
										bfw.write("UR");
										i--;
										j++;
									}
								}
								bfw.write("D"); // 다시 정상 궤도 진입시키기.
								trigger = true; // 왼쪽으로 진행시켜야 함. blockRow가 홀수일 때는 항상 오른쪽을 가리키다가 blockRow에 들어가기 때문에,
												// trigger를 뒤집어줄 필요가 있다.
								i++;
							}
							// 여기까지 회피기동

							if (trigger) {
								for (; j > 1; j--)
									bfw.write("L");
								trigger = false;
							} else {
								for (; j < col; j++)
									bfw.write("R");
								trigger = true;
							}
							if (i < row)
								bfw.write("D");
						}
						break;
					} else {
						boolean trigger = false;
						for (; i < row + 1; i++) {
							if (i == blockRow - 1) {
								while (true) {
									if (i + 1 == blockRow && j == blockCol) {
										bfw.write("RD");
										i++;
										j++;
									} else {
										bfw.write("D");
										i++;
									}
									if (j < col) { // 2x2에서는 바로 끝내야 하기 때문에 R이 실행되서는 안 됨.
										bfw.write("R");
										j++;
									} else
										break;
									bfw.write("U");
									i--;
									if (j < col) {
										bfw.write("R");
										j++;
									} else
										break;
								}
							}
							// 여기까지 회피기동

							if (trigger) {
								for (; j > 1; j--)
									bfw.write("L");
								trigger = false;
							} else {
								for (; j < col; j++)
									bfw.write("R");
								trigger = true;
							}
							if (i < row)
								bfw.write("D");
						}
						break;
					}
				}
			}
		}
		bfw.flush();
		bfw.close();
		bfr.close();
	}

	static class Block implements Comparable<Block> {
		int point;
		int row;
		int col;

		public Block(int point, int row, int col) {
			this.point = point;
			this.row = row;
			this.col = col;
		}

		@Override
		public int compareTo(Block b) {
			return this.point - b.point;
		}
	}

	/*
	 * static void print(int row, int col) {
	 * System.out.println("************행렬 그리기************"); for (int i = 1; i < row
	 * + 1; i++) { for (int j = 1; j < col + 1; j++) System.out.printf("%5d",
	 * matrix[i][j]); System.out.println(); }
	 * System.out.println("************행렬 그리기************"); }
	 */
}

95qwer 1년 전 0

반례 찾았습니다.

4 4
2 2 2 2
2 2 2 2
2 2 2 1
2 2 2 2

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

문제

문제

출처

ICPC

안녕하세요. 2873번 롤러코스터 문제에 대해 여쭙고 싶습니다.

95qwer 1년 전 0

95qwer 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말