[백준 / BOJ] - 1025번 ACM 호텔 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [10250] 

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

문제

 

 

높이가 H, 호수가 W개 만큼 있는 호텔에서 손님에게 방을 배정하려고 한다. 손님들은 엘레베이터에서 가까운 호실을 선호하고, 거리가 같다면 더 밑 층을 선호한다. 이 때, N번째의 손님이 배정받는 방 번호를 구하는 프로그램을 작성하는 문제이다.

 

풀이

 

규칙성은 다음과 같다.

1번째 온 손님은 1층 101호,

2번째 온 손님은 2층 201호,

H번째 온 손님은 H층 H01호,

H+1번째 온 손님은 1층 102호,

...

2*H 번째 온 손님은 H층 H02호 꼴이다.

 

즉, H번째마다 호수가 한개씩 늘어나고, 1이 늘어날때마다 층이 한개씩 늘어나는 규칙성을 가지고 있다.

 

이를 활용하여 나머지 연산과 나누기 연산을 적절히 사용하여 코드를 작성하면 시간초과 없이 문제를 해결할 수 있다. 

 

 

코드

 

#include <iostream>
using namespace std;
int main() {
    int num,yy,xx;
    cin >> num;
    int *h = new int[num];
    int *w = new int[num];
    int *order = new int[num];
    for(int i = 0; i < num; i++)
        cin >> h[i] >> w[i] >> order[i];
    for(int i = 0 ; i < num; i++)
    {
        xx = order[i] / h[i] + 1;
        yy = order[i] % h[i];
        if(order[i] % h[i] == 0)
        {
            yy = h[i];
            xx--;
        }
        if(xx < 10)
            cout << yy << "0" << xx << '\n';
        else
            cout << yy << xx << '\n';
    }
}

 

 

평가

 

호실이 yyxx형태로 적혀있다는것을 고려하여 yy와 xx를 각각 구하는 방식으로 규칙성을 찾아가는 방법이 유효한 풀이 접근 방식이다. 만약 xx가 10보다 작을경우, 0을 중간에 끼워넣어줘야한다. (예를 들어 1층 첫호실은 11호가 아니라 101호이다.)

또한 층으로 나눠떨어지는 경우 yy는 무조건 층수와 같아지므로, 예외처리를 통해 풀이가 가능하다.

본 문제의 정답률은 35%로, yy와 xx를 구분하고 나머지 연산을 활용해야 하는 점, 각종 예외처리를 진행해야 한다는점에서 조금 까다로웠던 문제이다.