acm 호텔 문제

문제

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

10250번: ACM 호텔

걷는걸 참 싫어하는 손님이다...ㅋㅋ

 

계획

<변수명 짓기>

테스트 케이스 개수 : test_num
호텔 층 수 : h
호텔 방 수 : w
몇 번째 손님 : n

 

호텔 방 -> boolean형 2차원 배열
boolean[][] rooms = new boolean[h][w];
** int형 2차원 배열을 이용해서 만드려고 했으나 int형은 4바이트, boolean형은 1바이트이므로 boolean형을 선택했다.

 

for문을 이차원 배열을 순환하며 손님이 들어간 방은 true로 설정.

제일 마지막 손님 n번째 손님의 방 번호를 출력하게 설계

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

public class Main
{
	public static void main(String[] args) {
		try {
		    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		    StringTokenizer st;
		    int h;// 층
		    int w; // 1층 당 방 개수
		    int n; // 몇 번째 손님

		    int test_num = Integer.parseInt(br.readLine());
		    for (int t = 0; t < test_num; t++) { 
		        st = new StringTokenizer(br.readLine());
    		    h = Integer.parseInt(st.nextToken()); 
    		    w = Integer.parseInt(st.nextToken()); 
    		    n = Integer.parseInt(st.nextToken());
    		    boolean[][] rooms = new boolean[h][w];
    		    boolean is_find = false; // 손님이 방을 찾았는지
    		    
		        for (int k = 0; k < n; k++) {
    		        for (int i = 0; i < w && !is_find; i++) {
        	            for (int j = 0; j < h && !is_find; j++) {
                            if (!rooms[j][i]) {
                                rooms[j][i] = true;
                                is_find = true;
                                if (k == n - 1) {
                    	            bw.write(String.valueOf(((j + 1) * 100) + i + 1) + "\n");
                    	        }
                                break;
                            }
        	            }
        	        }
        	        is_find = false;
    		    }
    		    rooms = new boolean[h][w];
		    }
		    
            br.close();
            bw.flush();
            bw.close();
		}
		catch (IOException e) {
		    System.out.println("IOException 발생");
		}
	}
}

복잡하다 복잡해

무려 4중 for문을 쓴 풀이이다.

일단 답은 맞췄는데 풀이가 좀 더러운 것 같아서 다른 분들은 어떻게 푸셨나 봤다.

 

다른 분들의 풀이를 봤더니, 이건 수학을 가지고 푸는 알고리즘 문제였다는 사실을 망각하고 있었다고 깨달았다.
이 문제의 원리를 생각해보면

1층부터 마지막 층까지 차례대로 배정됐다가 다시 1층으로 배정하는 원리이다.
이 규칙성을 이용해서

층 수 : 몇 번째 손님인지 % 층 수
몇 번째 방 : 몇 번째 손님인지 / 층 수 + 1

이런 식을 도출할 수 있다.

그 다음 층 수에 곱하기 100을 해주고, 거기에 몇 번째 방인지 구한 값을 더해주면 값이 나온다.

이렇게 구하면 n % h의 나머지가 나누어 떨어지는 경우가 있는데
만약 2층 호텔의 4번째 손님이 들어갈 층 수를 구하면 저 식으로는 0층이 나온다.
그러므로 나누어 떨어지는 구간만 +1을 해줘야한다.
마찬가지로 몇 번째 방인지를 구할 때도 -1을 해줘야한다.

 

다시 푼 풀이