백준 1982 호텔 예약 java

next(0,0,0) = 0 (어떠한 인원도 고려하지 않았으므로 당연히 0)
나머지 값은 Integer.MAX_VALUE 로 채우기 (여기서 Integer.MAX_VALUE = 도달 불가 라는 뜻이다.) 현재까지 고려한 방의 최대 수용 인원을 다 더한 값보다 m+f 값이 큰 경우는 계산하지 못하므로 Integer.MAX_VALUE로 값이 저장되어 있어야 한다.)

B. 점화식

현재 고려 중인 r번 방의 최대 수용 인원을 capacity라 해보자. 이때 다음 3가지 경우가 있다.

아직 예약 못 잡은 인원 중

남자만 채우는 경우

여자만 채우는 경우

커플 1쌍에게 방 통쨰로 주는 경우

1번과 2번의 점화식
1번과 2번의 경우, 남자 혹은 여자 인원 중 1명만 방에 넣는 경우부터 capacity 다 채워서 넣는 경우까지 경우의 수가 다시 나뉜다.


int cur_cost = dp[m][f][c];
if(cur_cost == Integer.MAX_VALUE) continue; // dp는 현재까지 처리현황인데 특정 영역의 비용이 아직 Integer.MAX_VALUE 이면 현재로서는 처리하지 못한 인원 수라는 뜻임.

// 현재 방에 수용량까지 남자만 집어넣는 경우
int next_cost = room.cost + cur_cost;
for(int male_cnt = 1; male_cnt <= room.capacity; male_cnt++){
    if(m + male_cnt > M) break;
    int nm = m + male_cnt;
    if(next_cost < next[nm][f][c]) next[nm][f][c] = next_cost;
}
// 현재 방에 수욜양까지 여자만 집어넣는 경우
for(int female_cnt = 1; female_cnt <= room.capacity; female_cnt++){
    if(f + female_cnt > F) break;
    int nf = f + female_cnt;
    if(next_cost < next[m][nf][c]) next[m][nf][c] = next_cost;
}

3번의 점화식
커플은 무조건 1쌍 1방임으로, 만약에 커플에 방을 준다면, dp 배열에서 여자,남자, 커플 수용 인원을 1씩 올리면 된다.


if(room.capacity >= 2 && c+1 <= C && m+1 <= M && f+1 <= F){
    int nm = m+1, nf = f+1, nc = c+1;
    if(next_cost < next[nm][nf][nc]) next[nm][nf][nc] = next_cost;
}

(3) DP 배열, next 스왑

A. 만약 그냥 `dp = next` 하면?

dp 변수와 next 변수가 같은 3차원 배열을 바라보게 된다.
점화식 맨 초기에 이전 값을 뜻하는 dp에서 r-1번 방까지 고려했을 때, dp(m,f,c)의 최소 비용을 cur_cost에 저장했던 것을 기억할 것이다.

만약 dp와 next가 같은 배열을 바라보고 있다면, 비교적 m,f,c가 큰 dp 배열의 cur_cost는 현재 next 계산으로 갱신된 m,f,c가 비교적 작은 dp 배열의 값이 다시 들어가게 된다. 즉 하나의 호텔방을 중복 사용하여 인원을 처리하는 잘못된 계산이 next에 들어가게 되는 것이다. 따라서 이전 방까지 고려한 dp와 next가 구분되도록 항상 swap을 통해서 구분해야 한다.

(4) 시간복잡도 분석 ⏳

남자,여자, 커플, 방 모두 최대 100개이다. 총 4차원 배열을 돌기 때문에 순회만 해도

10^{8}

이다.
이후 배열 안쪽에서 capacity만큼 추가로 배열을 순회하지만, 최대 5이다.
또한 이전값을 가리키는 dp(m,f,c)가 여전히 Integer.MAX_VALUE 이면 이후 계산을 안하는 식으로 계산을 많이 건너 뛴다. 따라서 4중 반복문 안쪽에서의 계산의 시간복잡도는 상수시간 정도로 본 시간복잡도에 많은 영향을 안 줄 것이라 판단된다.

따라서 최종 시간복잡도는

O(10^{8})

이다.

(5) 공간 복잡도

int 배열의 원소는 4byte를 차지한다. 이러한 원소를 3축으로 100개씩 가지면 총

10^6 \times 4byte = 4,000,000 \; byte

이다. 이는 4mb를 뜻한다. 만약 여기에 방 100개를 뜻하는 축을 더 넣어서 4차원 배열로 만들었다면 400mb이므로 문제에서 주어진 최대 공간복잡도인 128mb를 넘는다. 따라서 3차원 배열 2개를 가지고 운용해야 한다.

3. 코드 🌐


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

// 1982번 호텔 예약
public class Main {
    static class Room {
        int capacity;
        int cost;

        public Room (int capacity, int cost){
            this.capacity = capacity;
            this.cost = cost;
        }    }    static int M, F, R, C;
    static Room [] rooms;
    static int [][][] dp;
    static int [][][] next;
    public static void main(String[] args) throws IOException {
        init();
        for(int r = 1; r <= R; r++){
            Room room = rooms[r];

            for(int m = 0; m <=M; m++){
                for(int f = 0; f <= F; f++){
                    for(int c = 0; c<=C; c++){
                        next[m][f][c] = dp[m][f][c];
                    }                }            }
            for(int m = 0; m <= M; m++){
                for(int f = 0; f <= F; f++){
                    for(int c = 0; c <= C; c++){
                        int cur_cost = dp[m][f][c];
                        if(cur_cost == Integer.MAX_VALUE) continue; // dp는 현재까지 처리현황인데 특정 영역의 비용이 아직 Integer.MAX_VALUE 이면 현재로서는 처리하지 못한 인원 수라는 뜻임.

                        // 현재 방에 수용량까지 남자만 집어넣는 경우
                        int next_cost = room.cost + cur_cost;
                        for(int male_cnt = 1; male_cnt <= room.capacity; male_cnt++){
                            if(m + male_cnt > M) break;
                            int nm = m + male_cnt;
                            if(next_cost < next[nm][f][c]) next[nm][f][c] = next_cost;
                        }                        // 현재 방에 수욜양까지 여자만 집어넣는 경우
                        for(int female_cnt = 1; female_cnt <= room.capacity; female_cnt++){
                            if(f + female_cnt > F) break;
                            int nf = f + female_cnt;
                            if(next_cost < next[m][nf][c]) next[m][nf][c] = next_cost;
                        }                        // 커플을 집어넣을 수 있는 경우, 커플을 집어넣음.
                        if(room.capacity >= 2 && c+1 <= C && m+1 <= M && f+1 <= F){
                            int nm = m+1, nf = f+1, nc = c+1;
                            if(next_cost < next[nm][nf][nc]) next[nm][nf][nc] = next_cost;
                        }
                    }
                }
		        }
int [][][] temp = dp;
            dp = next;
            next = temp;
        }        int answer = Integer.MAX_VALUE;
        for(int c =0; c <= C; c++){
            answer = Math.min(answer, dp[M][F][c]);
        }        System.out.printf("%s", answer == Integer.MAX_VALUE? "Impossible" : answer);
    }
    public static void init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        F = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        rooms = new Room[R+1];
        next = new int[M+1][F+1][C+1]; // next[m][f][c] = dp 배열에서 현재 조회중인 방까지 합하여 남자 m명, 여자 f명, 커플 c명의 숙박을 처리했을 때 비용
        dp = new int[M+1][F+1][C+1]; // dp[m][f][c] = 현재까지 처리한 방으로 남자 m명, 여자 f명, 커플 c 명의 숙박을 처리했을 떄 비용
        for(int i = 1; i < R+1; i++){
            st = new StringTokenizer(br.readLine());
            rooms[i] = new Room (Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        for (int m = 0; m <= M; m++){
            for(int f = 0; f <= F; f++){
                for(int c = 0; c <= C; c++){
                    dp[m][f][c] = Integer.MAX_VALUE; // Integer.MAX_VALUE = 도달 불가 판정
                }
            }
        }
        dp[0][0][0] = 0; // 아직 방으로 아무 인원도 채우지 않음.
    }
}