글 읽기 - 21608번 질문 드립니다 ㅜ

jig6795 2년 전 0

주어진 조건대로 차례차례 풀었지만

테스크케이스는 통과하고 정답을 제출했을 때 바로 틀렸다고 나오네요

논리적으로 맞는 것 같은데 제가 어느 부분을 놓치고 있는 걸까요?

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

public class Main {

	static int[] dirR = { -1, 1, 0, 0 };
	static int[] dirC = { 0, 0, -1, 1 };
	static int N, result;
	static int[][] map; // 반의 자리 위치
	static int[][] students; // 각 학생이 좋아하는 4명
	static int[] sequence; // 선생님이 정해주는 순서
	static int[] score = { 0, 1, 10, 100, 1000 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		N = Integer.parseInt(br.readLine());
		map = new int[N + 1][N + 1];
		students = new int[N * N + 1][4];
		sequence = new int[N * N + 1];

		for (int i = 1; i <= N * N; i++) { // 총 명수는 N^2명
			st = new StringTokenizer(br.readLine(), " ");

			int num = Integer.parseInt(st.nextToken());
			sequence[i] = num;

			for (int j = 0; j < 4; j++) {
				students[num][j] = Integer.parseInt(st.nextToken());
			}
		}

		/* 1. 자리 배치 */
		/* 1-1. 가장 처음 사람은 무조건 (2,2)에 앉는다. */
		map[2][2] = sequence[1];

		for (int i = 2; i <= N * N; i++) {
			int cnt = 0;
			/* 1-2. 비어있는 칸 중 좋아하는 학생이 인접한 칸이 가장 많은 칸으로 자리 정한다. */
			int[][] likeCount = new int[N + 1][N + 1];

			/* 각 자리 인접한 칸 확인 */
			for (int j = 1; j <= N; j++) {
				for (int k = 1; k <= N; k++) {
					if (map[j][k] == 0) { // 만약 해당 자리가 비어 있다면 주변 확인
						for (int l = 0; l < 4; l++) {
							int nr = j + dirR[l];
							int nc = k + dirC[l];

							if (nr < 1 || nc < 1 || nr > N || nc > N || map[nr][nc] == 0)
								continue;

							for (int m = 0; m < 4; m++) {
								if (map[nr][nc] == students[sequence[i]][m]) {
									likeCount[j][k]++;
									break;
								}
							}
						}
					}
				}
			}

			/* 인접한 칸의 갯수 최대값 확인 */
			int max = Integer.MIN_VALUE;
			for (int j = 1; j <= N; j++) {
				for (int k = 1; k <= N; k++) {
					if (likeCount[j][k] != 0)
						max = Math.max(max, likeCount[j][k]);
				}
			}

			/* 여러 개가 존재할 수 있는 경우 확인 */
			for (int j = 1; j <= N; j++) {
				for (int k = 1; k <= N; k++) {
					if (likeCount[j][k] != max) {
						likeCount[j][k] = 0;
					} else {
						cnt++;
					}
				}
			}

			/* 1-3. 1-2.를 만족하는 칸 중 비어있는 칸이 가장 많은 칸 찾기 */
			if (cnt == 1) {
				a: for (int j = 1; j <= N; j++) {
					for (int k = 1; k <= N; k++) {
						if (likeCount[j][k] > 0) {
							map[j][k] = sequence[i];
							break a;
						}
					}
				}
			} else {
				int[][] emptyCount = new int[N + 1][N + 1];
				for (int j = 1; j <= N; j++) {
					for (int k = 1; k <= N; k++) {
						if (likeCount[j][k] > 0) { // 인접한 칸이 가장 많은 칸들 확인
							for (int l = 0; l < 4; l++) {
								int nr = j + dirR[l];
								int nc = k + dirC[l];

								if (nr < 1 || nc < 1 || nr > N || nc > N)
									continue;

								if (map[nr][nc] == 0) {
									emptyCount[j][k]++;
								}
							}
						}
					}
				}

				max = Integer.MIN_VALUE;
				for (int j = 1; j <= N; j++) {
					for (int k = 1; k <= N; k++) {
						if (emptyCount[j][k] != 0) {
							max = Math.max(max, emptyCount[j][k]);
						}
					}
				}

				/* 여러 개가 존재할 수 있는 경우 확인 */
				for (int j = 1; j <= N; j++) {
					for (int k = 1; k <= N; k++) {
						if (emptyCount[j][k] != max)
							emptyCount[j][k] = 0;
					}
				}

				/* 1-4. 좌상단에 최대한 가까운 위치에 배치 */
				b: for (int j = 1; j <= N; j++) {
					for (int k = 1; k <= N; k++) {
						if (emptyCount[j][k] > 0) {
							map[j][k] = sequence[i];
							break b;
						}
					}
				}
			}
		}

		/* 2. 만족도 계산 */
		int count = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				count = 0;

				for (int k = 0; k < 4; k++) {
					int nr = i + dirR[k];
					int nc = j + dirC[k];

					if (nr < 1 || nc < 1 || nr > N || nc > N)
						continue;

					for (int m = 0; m < 4; m++) {
						if (map[nr][nc] == students[map[i][j]][m]) {
							count++;
							break;
						}
					}
				}

				result += score[count];
			}
		}

		System.out.println(result);
	}

}

pichulia 2년 전 9

emptyCount[j][k] 가 0 인 자리에 학생을 배치해야만 할 수도 있습니다.

qwer15417 2년 전 0

그러게요 서로 달라야되는건데 좋아요 2개 뭐지;;

pichulia 2년 전 13

거 대충 알아들어주시면 안되나요...? ㅠㅠ

제가 공유한 반례는 "좋아하는 학생의 번호는 서로 다르다" / " 자기 자신을 좋아하는 경우는 없다" 가 그렇게 중요한 정보가 아닙니다.

핵심은 emptyCount[j][k] > 0 으로 처리하고 있는 이 게시글 코드의 로직이 잘못되었음을 인지시키는 것이였고,

따라서 이 게시글의 코드가 잘못 구현한 부분이 어디일지를 직관적으로 알아볼 수 있도록 고심해서 만든 예제입니다.

그걸 이렇게 받아치시면 슬퍼집니다....

문제의 조건을 만족하면서 이 코드를 터트리는, 여러분이 좋아하는 '비교적 비 직관적이지만 아무튼 문제의 채점데이터로써 가치가 있는' 반례 하나를 만들었습니다.

7번 학생의 경우, 자신이 좋아하는 학생이 주변에 한명도 없기 때문에 이 코드의 101번째 줄에서 비정상적으로 동작하게 됩니다.

만약 이 부분도 잘 고쳤다고 해도, 5번 학생의 경우, 가장 좋은 자리 두 곳이 모두 emptyCount 값이 0이여서 역시나 이 코드의 137번째 줄에서 비정상적으로 동작하게 됩니다.

pichulia 2년 전 2

@qwer15417

이 게시글의 코드같은 경우는 만족도 점수 계산 과정에서 오류가 있는 것이 아니고,

그 이전에 학생을 배치하는 과정에서 논리적인 오류가 있는 케이스였습니다.

그 논리적 오류가 어느 지점인지를 질문자가 이해할 수 있도록 만들기만하면 충분한 상황이었습니다.

따라서 만족도 점수 계산 과정에 영향을 주는 조건인 "어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다", "어떤 학생이 자기 자신을 좋아하는 경우는 없다." 를 만족하는 데이터를 반드시 사용할 필요가 없었던 것이죠.

(위 두 조건은 학생을 배치하는 과정에 영향을 주지 않기 때문에 머리 속으로나 손으로 로직을 따라가는데 전혀 문제가 없습니다.)

그것이 좋아요 2개를 받게 된 이유이지 않을까요...?

adxx 2년 전 0

답이 143인 예제 덕분에 편하게 맞았습니다 감사합니다

hky5820 1년 전 0

@pichulia

저는 작성자에 해당하는 문제는 아니였지만, 이미 차지한 자리를 놓치는 실수를 반례를 통해 찾아낼 수 있었습니다.

너무 좋은 반례 감사합니다.

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

문제

문제

출처

ICPC

21608번 질문 드립니다 ㅜ

jig6795 2년 전 0

pichulia 2년 전 9

qwer15417 2년 전 0

pichulia 2년 전 13

pichulia 2년 전 2

adxx 2년 전 0

hky5820 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말