오답노트 #10250 : ACM 호텔

풀이방법 및 문제점

2022.04.06

주어진 예제에 대하여 올바른 답을 출력하는 코드(코드 (1))는 쉽게 짤 수 있었다.

그러나 제출을 하면 틀렸다는 결과가 나왔다. 예외의 경우를 고려하지 못한 것이다.

아직도 수면패턴이 들쑥날쑥해서(빨리 고쳐야 한다...) 머리가 멍했기 때문에 내 손으로 반례를 찾기가 너무 귀찮았다.

그래서 그냥 즉시 질문 게시판으로 달려갔다.

나와 비슷한 수많은 사람들의 흔적이 있었고, 반례 하나를 금방 찾을 수 있었다.

 

첫 반례를 찾은 게시글 링크

 

일단 위 게시글에 있던

1
1 20 20

이 테스트케이스를 넣어보았더니

'120'호가 당연히 정답인데

'021'이라는 터무니없는 결과가 나왔다.

 

그래서 나는 내가 층이 하나 뿐인 경우를 고려하지 못하여 틀렸다고 생각했다.

 

층이 하나 뿐인 경우를 캐치하기 위해 if문을 추가하여 새로운 코드(코드 (2))를 짰다.

 

이제 층이 하나여도 올바른 값을 출력하였다.

그런데 제출을 해보니 또 틀렸다!

아직도 캐치를 못한 아예 다른 반례가 있거나,

층이 한 개인 경우를 포함하여 더 폭넓은 예외를 고려해야 하는데 그러지 못한 것이다.

 

다시 질문 게시판을 뒤져서 다음의 게시글을 발견했다.

 

도움이 된 반례 게시글 링크

 

어떤 분이 쓸만한 반례들을 잔뜩 모아서 올려둔 글이다. 감사합니다.

이 글에는 다음과 같은 테스트케이스가 실려 있다.

반례
20
1 1 1
1 5 4
1 9 4
1 20 20
2 2 4
2 4 4
2 10 4
6 12 6
6 12 7
6 12 10
6 12 12
6 12 55
10 10 91
10 10 99
30 50 31
30 50 72
99 99 1
99 99 99
99 99 100
99 99 9800

정답
101
104
104
120
202
202
202
601
102
402
602
110
110
910
102
1203
101
9901
102
9899

 

이걸 돌려보니 올바른 풀이법을 알 수 있었다.

바로, 고객의 순번을 층 수로 나눈 나머지가 0인 경우와 0이 아닌 경우로 나누어야 한다는 것이다.

층이 하나 뿐인 경우는 나머지가 0인 경우에 포함되는 하나의 예일 뿐이었다.

 

최종 정답 풀이는 정답 게시물에 적어두었다.

 

정답 게시물 바로가기

 

코드

Java(2022.04.06 (1))

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<t; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int f = Integer.parseInt(st.nextToken());
			st.nextToken();
			int n = Integer.parseInt(st.nextToken());
			
			int a = n%f;
			int b = n/f +1;
			
			System.out.print(a);
			if(b<10)System.out.print(0);
			System.out.println(b);
		}
	}

}

 

Java(2022.04.06 (2))

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<t; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int h = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(st.nextToken());
			
			int a, b;
			
			if(h == 1) a = 1;
			else a = n%h;
			
			if(h == 1) b = n;
			else b = n/h +1;
			
			System.out.print(a);
			if(b<10)System.out.print(0);
			System.out.println(b);
		}
	}

}