[알고리즘] ACM 호텔 백준 10250 JAVA 문제 풀이

문제

ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.

 

문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고).

 

이런 형태의 호텔을 H × W 형태 호텔이라고 부른다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.

그림 1. H = 6 이고 W = 12 인 H × W 호텔을 간략하게 나타낸 그림

방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다. 즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다.

 

손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸어야 하지만 301 호는 거리 1 만큼만 걸으면 되기 때문이다. 같은 이유로 102 호보다 2101 호를 더 선호한다.

 

여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다.

 

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수를 포함하고 있으며 각각 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다(1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W). 

 

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행을 출력하는데, 내용은 N 번째 손님에게 배정되어야 하는 방 번호를 출력한다.

예제 입력 1 복사

2
6 12 10
30 50 72

예제 출력 1 복사

402
1203

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2014 A번

 

 

백준 10250 ACM 호텔의 문제를 간단히 요약을 해보면 손님은 1층 부터 엘리베이터 가까운 순서 대로 배정이 될때

N번째 손님의 호수를 출력 하라는 문제 입니다.

 

그럼 호수는 층수 + 호수로 구성이 되는데요. 

 

층수를 구하고 호수를 구해서 출력을 하면 되겠죠? ^.^

그럼 우선 층수를 floor이라고 하고. 호수를 엘리베이터와의 거리인 distance라고 가정을 하고 

 

반복문을 이용하는 코드를 작성을 해보면 아래와 같습니다. 

int floor =1;     ==> 1층 부터 시작이 되니까 층수를 1로 초기화를 하고
innt distance =1; ==> 엘리베이터에서 가장 가까운 방을 배정을 해야 되니. 1로 초기화
while(--N >0){    ==> --N은 101호를 먼저 배정을 하니까... N-1 번만큼 반복문을 수행
	floor++;      ==> 101호가 배정이 되었으므로 엘리베이터에서 가장가까운 다음층으로 이동
    if(floor > H){   ==>  floor값이 건물의 층수인 H보다 높으면 floor를 다시 1층으로 초기화 
    floor =1;
    distance++;     ==> 다음 호수를 배정 
    }
  }

 

위의 코드는 방을 기본 적으로 요구사항에 맞게 차례로 배정하는 코드인데. 

 

우선 문제에서 입력을 받는건 입력 되는 테스트 케이스 수인 T가 입력 되고 

다음  줄에 호텔의 충수인 H와 각 층의 객실수인 W와 손님의 번호인 N이 순차적으로 입력 됩니다. 

 

방의 호수가 어떻게 구해지는지 계산을 해보면. 예를 들어 110번째 손님과 111번째 손님의 호수를 구해보면. 

위의 그림과 같이

 

110번째 손님은 10층의 11호 죽 1011호가 되고.

111번째 손님의 방은 1층 12호가 됩니다. 

 

그럼 이 층과 호수를 어떻게 구하는지 살펴 보면. 

distance는 10명 마다 한개씩 증가를 한다는 것을 알수가 있을 겁니다.

 

위에서 보면 1층 1호의 손님인 1번손님의 다음 번 102호의 손님은 11번째 손님이 되는것을 볼수가 있습니다. 

이걸 수식으로 표현해 보면. 

 

(N - 1) %H +1을 하면 층수가 나오구요. 

(N -1) /H +1을 하면 호수가 나옵니다. 

 

그럼 이 수식을 위의 반복문을 이용한 코드가 아니라 수식을 이용해서 구하는 코드를 정리를 해보면

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {               ==> 테스트 케이스 수 만큼 반복을 하고
            int H = sc.nextInt();       ==> 호텔의 층수를 입력 받고
            int W = sc.nextInt();       ==> 각층의 호수 갯수를 이력 받고
            int N = sc.nextInt();      ==> 몇번째 손님인지 수를 입력 받고

            int floor = ((N - 1) % H) + 1;  // [1, H]   ===> 층수를 구하고 
            int distance = (N - 1) / H + 1; // [1, W]   ==> 호수를 구하고. 
            System.out.printf("%d%02d\n", floor, disatnce);  ==> 층수와 호수를 출력
        }
    }
}

 

"%d%02d\n"는 Java에서 printf나 String.format을 사용할 때 형식을 지정하는 포맷 문자열입니다. 이 포맷 문자열을 사용하여 정수 값을 특정 형식으로 출력할 수 있습니다. 각 부분의 의미를 설명하면 다음과 같습니다:

• %d: d는 decimal(10진수) 정수를 나타냅니다. 따라서, %d는 정수를 그대로 출력합니다.
• %02d: 이 부분은 두 자리의 10진수 정수를 출력하되, 만약 숫자가 두 자리가 되지 않으면 앞에 0을 추가합니다. 예를 들어 5라는 숫자를 출력하면 05가 출력됩니다. 02에서 0은 앞에 채워질 문자(0)를 의미하고, 2는 최소 자릿수를 의미합니다.
• \n: 개행 문자로, 줄바꿈을 의미합니다. 이 문자가 있으면 출력이 끝난 후에 다음 출력이 새로운 줄에서 시작됩니다.