[C++/Baekjoon] ACM 호텔

스스로 생각하며 시행착오를 좀 거친 문제여서 블로그에 기록 해 두고자 한다.

 

문제

ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다.

고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다.

여러분은 지우를 도와 줄 프로그램을 작성하고자 한다.

즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.

 

문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자.

각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99).

그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고).

이런 형태의 호텔을 H × W 형태 호텔이라고 부른다.

호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다.

또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.

 

그림 1

방 번호는 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호, 3호, 4호 … 이런 라인으로 말이다.

 

그렇게 하여 아래 코드 부분처럼 수학적으로 규칙을 찾아서 나름 코드를 짜 보았다.

 

#include<iostream>
#include<string>

using namespace std;

int main(){
    int count;
    cin>>count;
    
    int row,column,guest; // 행, 열, 손님
    
    for(int i=0;i<count;i++){
        cin>>row>>column>>guest;
        
        int floor = guest % row;
        int room = guest / row + 1;
        string roomNum;
        if(room < 10){
            roomNum = to_string(floor) + "0" + to_string(room);
        }else{
            roomNum = to_string(floor) + to_string(room);
        }
        cout<<roomNum<<endl;
        
    }
    
    
}

 

그런데 문제가 생기게 되었다.

 

위 코드대로 하게 되면 층 수와 고객의 수가 같을 경우 나머지가 0으로 나와 제대로 된 호수가 적히지 않는 것이었다.

 

그래서, 생각을 해 보게 되니 층수만큼 위로 올라가게 되기 때문에 손님 수가 층수랑 같거나 작게 되면 무조건 1호 라인으로 고정되게 된다는 점이 생각나게 되었다.

 

따라서 코드를 아래와 같이 고쳐주게 되었다.

 

#include<iostream>
#include<string>

using namespace std;

int main(){
    int count;
    cin >> count;

    int row, column, guest; // 행, 열, 손님

    for (int i = 0; i < count; i++) {
        cin >> row >> column >> guest;

        int floor;
        int room;
        string roomNum;

        if (row >= guest) { // 1호 라인으로만 커버 가능
            roomNum = to_string(guest) + "01";
            cout << roomNum<<endl;
            continue;
        }
        else {
            floor = guest % row;
            room = guest / row + 1;
        }
        
        roomNum = room < 10 ? roomNum = to_string(floor) + "0" + to_string(room) : roomNum = to_string(floor) + to_string(room);

        cout << roomNum << endl;

    }
    
}

그런데 여기서 또 되지 않아서 반례를 찾다가 다른 분들의 반례를 참고하게 되었다.

 

그 중에서 10 10 100이라는 반례를 찾게 되었다.

 

위 코드대로 하게 되면 row 값보다 guest 값이 크기 때문에 조건문에서 else로 가게 되고, else에서 floor 값이 0이 되게 된다. (guest가 row의 배수이기 때문에 딱 맞아 떨어진다.)

 

그리고 room 값도 11이 나오게 되어 원래대로라면 1010호에 있어야 하는데 이상하게 나오게 되는 것이다.

 

이에, 배수에 대한 조건을 추가 해 주었다.

 

#include<iostream>
#include<string>

using namespace std;

int main(){
    int count;
    cin >> count;

    int row, column, guest; // 행, 열, 손님

    for (int i = 0; i < count; i++) {
        cin >> row >> column >> guest;

        int floor;
        int room;
        string roomNum;

        if (row >= guest) { // 1호 라인으로만 커버 가능
            roomNum = to_string(guest) + "01";
            cout << roomNum<<endl;
            continue;
        }
        else {
            floor = (guest % row) == 0 ? guest / row : guest % row;
            room = (guest % row) == 0 ? guest / row : guest / row + 1;
        }
        
        roomNum = room < 10 ? roomNum = to_string(floor) + "0" + to_string(room) : roomNum = to_string(floor) + to_string(room);

        cout<<stoi(roomNum)<<endl;

    } 
    
}

 

100 / 10의 사례를 보고 100 % 10이 0일 때는 그냥 나눈 값이 들어가게 해 주면 되겠다고 생각을 했다. (생각이 부족했다..)

 

위와 같이 바꾸어 주고, 10 10 100을 넣어 주니 1010이 나오고, 추가적으로 2 4 4 로 테스트를 해 보니 202가 나오게 되어 맞은 줄 알았다.

 

하지만, 2 4 8을 넣어보게 되니 404가 나오게 되었다. 2층까지 있는데 4층이 있는 것처럼 나오게 된 것이다.

 

곰곰히 생각을 해 보니 row(층)의 배수이면, 항상 최상층에 위치하게 되겠다는 생각을 했다.

 

예를 들어 2층 건물에 4번째 손님은 202호, 8번째 손님은 204호 2n 번째 손님은 2층의 n번째 방에 위치하게 되는 것이다.

따라서 그에 맞게 코드를 고치면

 

코드

#include<iostream>
#include<string>

using namespace std;

int main(){
    int count;
    cin >> count;

    int row, column, guest; // 행, 열, 손님

    for (int i = 0; i < count; i++) {
        cin >> row >> column >> guest;

        int floor;
        int room;
        string roomNum;

        if (row >= guest) { // 1호 라인으로만 커버 가능
            roomNum = to_string(guest) + "01";
            cout << roomNum<<endl;
            continue;
        }
        else {
            floor = (guest % row) == 0 ? row : guest % row;
            room = (guest % row) == 0 ? guest / row : guest / row + 1;
        }
        
        roomNum = room < 10 ? roomNum = to_string(floor) + "0" + to_string(room) : roomNum = to_string(floor) + to_string(room);

        cout<<stoi(roomNum)<<endl;

    } 
    
}

 

floor에 있는 삼항 연산자 가운데 부분에 row를 넣어 주었다. 즉, 최상층에 고정되게 해 준것이다.

 

이렇게 반례를 참고해서 풀었는데.. 조금 더 반례를 생각 해 내는 연습을 해야겠다..

(체계적인 시스템으로?)

 

• 같은 경우
• 배수
• 크기 비교 케이스
• 층이 1층인 건물

이렇게 리스트를 만들어 표로 만들어서 반례를 따져 보아야겠다는 반성을 하였다.

 

아, 그리고 문제 난이도를 보니 브론즈 3이던데... (롤도 브론즈인데) 고전했다는게 너무 아쉽다. 더 노력해야겠다..