[백준/Java]Q10250

백준 알고리즘 8단계 기본 수학1 10250번 문제입니다.

---

Q. ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하시오.

그림 출처 : https://www.acmicpc.net/problem/10250

[입력]
- 첫 줄에 테스트 데이터 개수 T가 주어진다.
- 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타내는 세 정수 H, W, N이 주어진다.

[조건]
- 1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W
- 호텔은 직사각형 모양이고 각 층에 W 개의 방이 있는 H 층 건물이다.
- 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정한다.
- 모든 방은 비어있다고 가정하고 N 번째로 도착한 손님에게 배정될 방 번호를 계산한다.
 

풀이

이 문제는 규칙을 찾아서 풀 수 있었다.

먼저 조건대로 보면 층 수가 3이고, 각 층의 방수는 5, 6번째 손님을 받을 때, 손님은 302번 방을 배정받게 될 것이다.

여기서 규칙은 101 > 201 > 301 > 102 > 202 > 302 순으로 순서가 정해진다는 것이다.

아래 상황에서 테스트 케이스를 정의해봤다. H : 3, W : 5

1. N : 5 => 202(2층)
2. N : 7 => 103(1층)
3. N : 12 => 304(3층)
4. N : 13 => 105(2층)

여기서 층 수에 대한 규칙을 발견할 수 있었다. N번째의 층 수는 N을 H(층 수)로 나눈 나머지값이 된다. 여기서 나머지 값이 0이면 총 층 수인 H가 됐다. 각 열의 개수가 H이기 때문이다.

1. 5 % 3 = 2
2. 7 % 3 = 1
3. 12 % 3 = 0
4. 13 % 3 = 1

이제 번호만 구할 수 있으면 될 것 같다.

번호를 유심히 보면 N이 1일 때 101, 2일 때 201, 3일 때 301, 4일 때 102, 5일 때 202, 6일 때 302로 N이 3의 배수인 경우에는 N / H이 번호가 되는 것을 알 수 있었다.

1. N : 3 => 1(3 / 3)
2. N : 6 => 2(6 / 3)
3. N : 9 => 3(9 / 3)

이 외의 경우는 N을 H로 나눈 값 +1이 번호가 된다.

1. N : 2 => 1((2 / 3) + 1) 
2. N : 7 => 3((7 / 3) + 1) 
3. N : 13 => 5((13 / 3) + 1) 

문제를 풀다보면 방 수는 필요가 없음을 알 수 있다.

 

소스

package com.baek.algo;

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

public class Q10250 {

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

		int t = Integer.parseInt(bf.readLine());

		for(int i = 0; i < t; i++) {
			String arr[] = bf.readLine().split(" ");

			int h = Integer.parseInt(arr[0]);
			int w = Integer.parseInt(arr[1]);
			int n = Integer.parseInt(arr[2]);

			int room   = 0;
			int floor  = n % h;
			int number = (n / h) + 1;

			if(floor == 0) {
				room = (h * 100) + (n / h);
			} else {
				room = (floor * 100) + number;
			}

			System.out.println(room);
		}

		bf.close();
	}
}