[백준] 10250번 : ACM 호텔 - Python

문제

 

https://www.acmicpc.net/problem/10250

10250번: ACM 호텔

 

 

풀이

우선 조건을 보면 거리가 같을 때에는 아래층 방을 선호한다는 것이 적혀있다. 이는 거리가 짧다면 윗층을 선택할 수도 있다는 것인데, 즉 N번째 손님의 방 호수를 결정하기 위해서는 아래층에서 윗층으로 쌓아가듯이 순서대로 진행하면 된다는 것이다. 

 

그림으로 나타낸다면 다음과 같다.

 

그런데 다음과 같이 진행하다보면 규칙이 눈에 보인다.

H(입력된 층수)는 N의 크기에 따라 층수는 1 ~ H 의 값으로 반복될 것이다. 고등학교 때 지겹도록 했던 나머지 정리가 생각나지 않는가?

그렇다! 나머지 정리를 이용하면 손님의 방의 층수는 간단히 구할 수 있을 것이다!

 

그렇다면 호수는 어떻게 구하는 것이 좋을까? 

 

위의 그림으로 예를 들어보자. 

N이 10인 경우 층수는 앞선 나머지 정리에 의해 10%6 = 4 로 단번에 4층에 묶을 것이라는 것을 알 수 있다.  

그렇다면 이제 호수를 구할 것이다. 손님의 방의 호수는 아래에서 위로 차곡히 쌓이게되니 H의 영향을 받아 결정된다. 

해당 예시에서도 마찬가지로 N이 10이기 때문에 6층 만큼 다 찬 후에는 다시 1층으로 내려와 새롭게 쌓게된다. 즉 6의 배수배만큼씩 채워나간다는 것이다. 즉 N=10을 H로 나눈 후 올림을 해주는 값이 해당 손님의 호수일 것이다.

여기서는 10/6 = 1.6, 올림하여 2가 해당 손님의 호수가 되는 것이다. 

그러나 주의 할 점이 있다. 

만약 H의 크기가 W크기보다 더 크다면 오류가 발생 할 것이다.

이를 위해 n/h의 결과에 w로 나머지 정리를 이용해주어야한다.

 

코드는 다음과 같다.

import math

t = input()
t = int(t)


for i in range(t):
    h, w, n = map(int, input().split())
    roomHeight = n%h
    roomNumber = (math.ceil(n/h))%w
    if roomHeight == 0 :
        roomHeight = h
    if roomNumber == 0:
        roomNumber = w   
    roomHeight = roomHeight * 100
    room = roomHeight + roomNumber
    print(room)