백준 1106 호텔 python, java

1차원 배열을 만들어서 DP 로 해결했다.
DP[i] 값은 i명의 고객을 늘리는데 필요한 최소 금액이다.

📜 문제 바로 가기 : 호텔

제출코드

파이썬

import sys
sys.stdin = open('ee.txt', 'r')
input = sys.stdin.readline

C, N = map(int, input().split())
spare = 101
DP = [1000*100] * (C+spare) # idx 명을 유치하는데 필요한 가장 작은 비용

table = []
for _ in range(N):
    c, p = map(int, input().split()) # c : 비용, p : 홍보인원
    DP[p] = min(DP[p], c)
    table.append((c, p))

for i in range(1, C+spare):
    for (c, p) in table:
        if i - p > 0:
            DP[i] = min(DP[i], DP[i-p] + c)

print(min(DP[C:]))

자바

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

public class Main {
    static final Main mySolve = new Main();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int C = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] DP = new int[C + 101];

        for (int i = 0; i < C + 101; i++) {
            DP[i] = 100*1000;
        }

        Table [] tables = new Table[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int people = Integer.parseInt(st.nextToken());
            tables[i] = new Table(cost, people);
            DP[people] = mySolve.minMethod(DP[people], cost);
        }

        for (int i = 0; i < C + 101; i++) {
            for (Table tb : tables) {
                if (i - tb.people > 0) {
                    DP[i] = mySolve.minMethod(DP[i], DP[i-tb.people] + tb.cost);
                }
            }
        }

        int ans = DP[C];
        for (int i = C+1; i < C + 101; i++) {
            ans = mySolve.minMethod(ans, DP[i]);
        }

        System.out.println(ans);
    }


    public int minMethod(int a, int b) {
        if (a > b) {
            return b;
        }
        return a;
    }
}

class Table {
    int cost;
    int people;

    public Table(int cost, int people) {
        this.cost = cost;
        this.people = people;
    }
}

---

접근방법

DP 배열은 각 index 명을 늘리는 데 필요한 최소 금액이다.
각 도시에 입력값을 받으면서 배열값을 초기화 해준다. 이때 기존 배열값이 있을 수 있으므로 비교해서 작은 값을 넣어준다.

그 후 1명 부터 C + 100 명까지 계산을 해준다.
각 도시의 홍보비용(c)과 기대인원(p)을 확인하면서 DP[i-p] 에서 +c 를 한 값과 현재의 값 DP[i] 를 비교해 보다 작은 값을 채워 넣는다.

100명의 여유분을 준 이유는 C 명 유치보다 C + x 명 유치가 더 저렴한 경우의 수가 있을 수 있기 때문이다.
이때문에 DP 배열값을 모두 채운 후에도 C ~ C + 100 값 사이에서 가장 작을 값을 출력해준다.