lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



입출력 예시

Input 

2
6 12 10
30 50 72

Output 

402
1203


문제 풀이

이 문제는 조건식을 잘 세워야 한다. 호텔의 방을 배정할 조건을 정해보자.

  • 엘리베이터에서 가까운 순으로 방을 배정한다.
  • 거리가 같다면, 낮은 층수부터 방을 배정한다.


아래 예시를 보면 빠르게 이해할 수 있다.

방 번호의 경우 YYX 또는 YYXX 형식으로 이루어진다. Y는 층수, X는 호수 즉, 엘리베이터와의 떨어진 거리이다.
위 예시를 보면 층수 H가 6이고, 호수 W가 12인 호텔에서 10(N)번째 손님의 경우 402호를 배정받게 된다.


층수 구하기

먼저 N번째 손님이 배정받을 방의 층수를 구해보자. 입력받은 H를 활용해 어떻게 층수를 구할 수 있을까?
위 예시처럼 10번째 손님일 경우 1층에서 6층까지는 자리가 없고 다시 1층부터 시작하여 4층에서 방을 배정받을 수 있다.
나머지 연산을 해보니 10%6으로 4층에 배정받음을 알 수 있었다.

  • 층 수: N % H

그런데, 반례를 찾아보니, N번째 손님이 정상층에 배정받아야 할 경우를 고려해야 한다.
예를 들어 6층 호텔에 6번째 손님일 경우 정상층인 6층을 배정받아야 하는데 위 식대로라면, 6%6=0 되어 0층이 되어버린다.
그래서 정상층일 경우엔 나머지연산을 하지 않고 H층으로 부여해야 한다.

  • 정상층 배정받을 경우 층수: H
  • 그 외 층수: N % H

그리고 방 번호는 YXX 또는 YYXX 형식으로 최소 100 자리수를 지켜야 한다. 구한 층수에 100씩 곱하면 된다.

  • 정상층 배정받을 경우 층수: H * 100
  • 그 외 층수: (N % H) * 100



호수 구하기

이제 층수를 구했으니, 호수만 구하면 된다. 호수는 엘리베이터로부터 떨어진 거리이다.
N을 H로 나눈 몫에서 +1을 하면 거리를 구할 수 있다.
왜 +1을 하냐면, N=10을 H=6로 나눈 몫은 0이지만, 실제 호수는 1부터 시작하기 떄문이다.

  • 호수: (N / H) + 1

그런데, 호수를 구할 때도 정상층에 배정받아야 할 때 고려해야 할 점이 있다.
예를 들어 H=6, N=6일 때 601호를 배정받아야 하는데 위 식을 적용하여 호수를 구하면 (6/6)+1 로 602호라고 나온다.
그렇기에 위 정상층을 배정받을 경우 층수 구할 때와 동일하게 +1을 해주지 않고 N/H만 해주면 된다.

  • 정상층 배정받을 경우 호수: N / H
  • 그 외 호수: (N / H) + 1



W는 필요없다?

원래 입력받을 때 H W N 형식으로 3개의 입력이 주어지는데 문제를 풀다보면 W가 필요없었다.
테스트케이스에서 N이 H*W값보다 큰 값으로 주어지지 않기 때문임을 알 수 있었다.
고로 W는 없어도 됨을 인지할 수 있었다.


이제 위에서 도출한 아이디어를 가지고 코드를 작성해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int rs_H = 0;
int rs_W = 0;

if(N%H == 0) { // 정상층을 배정받아야 하는 경우
    rs_H = H * 100;
    rs_W = N / H;
    bw.write(rs_H+rs_W+"\n");

}
else { // 그 외 층을 배정받아야 할 경우
    rs_H = (N % H) * 100;
    rs_W = (N / H) + 1;
    bw.write(rs_H+rs_W+"\n");
}

배정받을 층수를 rs_H, 호수를 rs_W 변수에 받아 테스트케이스마다 출력하도록 작성하였다.
층수와 호수 모두 정상층을 배정받을 경우와 아닌 경우를 구분지어 조건을 줄 수 있기에 합칠 수 있었다.


작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int H = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());

            int rs_H = 0;
            int rs_W = 0;

            if(N%H == 0) {
                rs_H = H * 100;
                rs_W = N / H;
                bw.write(rs_H+rs_W+"\n");

            }
            else {
                rs_H = (N % H) * 100;
                rs_W = (N / H) + 1;
                bw.write(rs_H+rs_W+"\n");
            }
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

  • 알고리즘 문제에서 수학적 계산이 필요한 문제에서는 특정 수로 나눈 나머지나 몫을 유심히 보고 패턴을 유추해야 함을 느꼈다.

출처

You may also enjoy