10250번 - ACM 호텔

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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int H, N, Q, R;
		StringBuilder sb = new StringBuilder();
		for(int t=0;t<T;t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			H = Integer.parseInt(st.nextToken());
			st.nextToken();
			N = Integer.parseInt(st.nextToken())-1;
			Q = N / H;
			R = N % H;
			sb.append(R+1);
			if(Q < 9) {
				sb.append(0);
			}
			sb.append(Q+1);
			sb.append("\n");
		}
		System.out.println(sb);
		br.close();
	}
}

 

난이도에 비해 말이 길어서 힘겨운 문제입니다.

 

이 풀이의 경우 W값이 주어지나 사용할 필요가 없었는데 H값 만으로도 모든 답을 구할 수 있습니다. (어차피 모든 층의 1호를 채우면 1층부터 2호를 채우기 시작하므로 굳이 호수가 얼마나 있는지 몰라도 N과 H만으로 추론이 가능합니다.)

 

백준 기준 1위가 72ms이고 위 코드는 84ms인데 W를 사용하지 않은 영향이 크지는 않다고 생각합니다.

 

문제를 해결하기 위해서는 N번째 손님이 몇 층, 몇 호에 들어갈 지를 알아야 하는데 결과적으로 말하면 N-1을 H로 나눈 몫과 나머지를 통해 호수와 층을 구할 수 있습니다.

 

가령 6층 건물이라고 할 시 1, 2, 3, 4, 5, 6번째 손님이 1호에 들어가게 되는데 7~12번째 손님이 2호에 들어가는 식이라는 것을 쉽게 유추할 수 있습니다.

 

이 때 사용하는 트릭이 저 수들을 하나씩 앞으로 당기는 것입니다.(당기지 않으면 6일때 1이 되어버립니다.)

0~5번째 손님이 1호, 6~11번째 손님이 2호인 식으로 당기게 되면 손님의 순서를 6으로 나눈 몫이 각각 0, 1, 2식으로 증가하는 것을 발견할 수 있습니다.

 

어차피 층수 단위로 끊어지기 때문에 약간의 조절을 통해 몫과 나머지를 사용해낼 수가 있습니다.

그래서 구한 몫에 1을 더해주면 손님이 몇 호에 들어가는 지를 알 수 있습니다. 이게 한자리일 경우에는 앞에 0을 붙여줘서 1층의 경우 101과 같이 나올 수 있도록 합니다. 물론 두 자리면 110과 같이 그대로 나옵니다.

 

마찬가지로 0~5에 해당하는 나머지에 1을 더해주면 손님이 들어가는 층 수가 됩니다. 이제 층수와 호수를 모두 구했기 때문에 StringBuilder를 사용해서 더해주기만 하면 끝입니다. 테스트케이스가 많기 때문에 모든 출력을 StringBuilder에 넣고 한 번에 출력합니다.