글 읽기 - 경찰차문제 왜 틀렸는지 모르겠습니다

leeho203 7년 전 0

제가 멍청한건지 아무리 생각해봐도 소스가 왜 틀렸는지 잘 모르겠습니다

출력은 제대로 맞게 나오는 것 같은데 틀렸다면 반례가 되는 테스트 케이스가 어떤 것이 있을까요??

고수님들 도와주시면 감사하겠습니다~!

import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int posX1 = 1;
		int posY1 = 1;
		int posX2 = n;
		int posY2 = n;
		int total = 0;
		String result = "";

		int crimeCase = sc.nextInt();
		for (int i = 1; i <= crimeCase; i++) {
			int crimeX = sc.nextInt();
			int crimeY = sc.nextInt();
			int dist1 = Math.abs(crimeX - posX1) + Math.abs(crimeY - posY1);
			int dist2 = Math.abs(crimeX - posX2) + Math.abs(crimeY - posY2);
			if (dist1 > dist2) {
				posX2 = crimeX;
				posY2 = crimeY;
				total += dist2;
				result += "2";
			} else {
				posX1 = crimeX;
				posY1 = crimeY;
				total += dist1;
				result += "1";
			}

			if (i != crimeCase) {
				result += "\n";
			}
		}

		System.out.println(total);
		System.out.print(result);

	}
}

etaehyun4 7년 전 0

그리디 방법을 쓰셨는데 이 문제의 정해는 아닙니다. 만약 dist1 과 dist2 가 같으면 무엇으로 이동할지 쉽게 결정할 수 없겠지요. N = 6, M = 2 { (3, 3), (1, 1)} 이 반례가 되겠네요.

그리고 result를 출력 할 때 문제에서는 한 줄에 하나씩 출력을 요구하고 있습니다

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

문제

문제

출처

ICPC

경찰차문제 왜 틀렸는지 모르겠습니다

leeho203 7년 전 0

etaehyun4 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말