백준 10250번: ACM 호텔 [구현][탐색][시뮬레이션] - Java

 

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

10250번: ACM 호텔

호텔에 N번째로 도착한 손님에게 배정될 방 번호를 계산하는 알고리즘이다.

엘리베이터에서 호텔 방까지의 거리를 기준으로 적게 걷는 것을 선호하고, 같은 거리라면 아래층을 선호한다.

 

위 문제를 푸는 방법은 2가지가 있다.

 

 

(1)  첫 번째 방법- 완전탐색

호텔 101호부터 H W호 까지를 모두 계산하는 방법이 있다.

101,201,301...H01... 102,202,302...H02... 이렇게 위로 올라가는 방식의

반복문을 이용해서 일일히 모든 case를 계산할 수도 있다. 그렇게되면 시간복잡도는 O(N). 

//반복문을 이용하여 방번호를 구하기

			int curH = 1;
			int curW = 1;
			for (int i = 1; i <= N; i++) {
				if(i==N) {
					System.out.println(curH+""+String.format("%02d",curW));
				}
				curH++;
				if(curH>H) {
					curH=1;
					curW++;
				}
			}

728x90

 

 

(2) 두 번째 방법 - 공식 계산

일일히 1~N까지 방번호를 부여하지 않아도 특정 N번째의 경우의 방번호를 계산할 수 있다.

(N번째 손님 / 호텔높이 H) 를 하게되면  몫과 나머지로 호텔층수와 호실을 알 수 있다.

몫+1을 호실로 보고, 나머지를 층수로 본다.

단, 나머지가 0일경우에는 해당 호텔의 가장 최상단에 있는 방이라는 의미이니 잘 처리를 해두자

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());

		int TC = Integer.parseInt(st.nextToken());
		
		for (int tc = 0; tc < TC; tc++) {
			//입력
			st = new StringTokenizer(br.readLine());
			int H = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());
			int N = Integer.parseInt(st.nextToken());
			
			//방번호 구하기
			int resW = N%H == 0 ? N/H : (N/H)+1;
			int resH = N%H == 0 ? H : N%H;
            
			int result = Integer.parseInt(resH+""+String.format("%02d", resW));

			System.out.println(result);

		}
		
	}

}