백준 1106 호텔[JAVA]

🔗링크

1106 호텔 Gold5

⚠️문제

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

🔍분석

---

투자하는 돈의 최솟값을 구하는 문제인데, dp로 접근해 보았다. 1명일 때, 가장 작은 돈이 드는 경우, 2원일 때, (1명일 때 + 1원짜리 가장 작은 돈이 드는 경우) 와 (2명 이상인 경우 중 가장 작은 돈이 드는 경우), 3원일 때, 4원일 때... 계속 반복하여 접근시킬 수 있었다. 100원일때 10명 4명 2명 있으면 (90명일때 최소 + 10명), (96명일때 최소 + 4명), (98명일때 최소 + 2명) 중 가장 작은 값을 고르면 최솟값이 될 것이다. 이와 같은 규칙으로 진행해봤다

---

1. 변수 선언은 아래 코드와 같이 하였다. cost와 peson을 가진 객체를 생성했고 해당 객체를 리스트로가진 도시 배열을 선언했다.

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static MarketingCost[] city;
    static int result = 987654321;
    static int[] array;
    static int N, C;
    
    class MarketingCost {
    int cost;
    int person;

    public MarketingCost(int cost, int person) {
        this.cost = cost;
        this.person = person;
    }
}

 2.dp값을 저장하는 array값을 최댓값이 넘는 값으로 설정을 해주고 0인덱스를 0으로 설정해주었다. 계산하다 인덱스가 -가 될경우 인덱스를 0으로 바꿔주고 0을 반환하기 위함이였다.(만약 -1명이던 -2명이던 드는 비용은 0이니깐)  이후 값들을 저장해준다.

        city = new MarketingCost[C];
        array = new int[1101];
        Arrays.fill(array, 987654321);
        array[0] = 0;

        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            city[i] = new MarketingCost(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

3.이후 처음에 설명했던대로 천천히 전체 경우의 수를 따져가며, 배열을 채운다. 

        for (int i = 1; i <= N; i++) {
            for (MarketingCost m : city) {
                int index = 0;
                if (i - m.person < 0){
                    index = 0;
                }else{
                    index = i - m.person;
                }

                array[i] = Math.min(array[index] + m.cost, array[i]);
            }
        }

        for (int i = N; i <= N; i++) {
            result = Math.min(result, array[i]);
        }

 

---

✔전체 코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static MarketingCost[] city;
    static int result = 987654321;
    static int[] array;
    static int N, C;

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        city = new MarketingCost[C];
        array = new int[1101];
        Arrays.fill(array, 987654321);
        array[0] = 0;

        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            city[i] = new MarketingCost(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        for (int i = 1; i <= N; i++) {
            for (MarketingCost m : city) {
                int index = 0;
                if (i - m.person < 0){
                    index = 0;
                }else{
                    index = i - m.person;
                }

                array[i] = Math.min(array[index] + m.cost, array[i]);
            }
        }

        for (int i = N; i <= N; i++) {
            result = Math.min(result, array[i]);
        }

        System.out.println(result);
    }

}

class MarketingCost {
    int cost;
    int person;

    public MarketingCost(int cost, int person) {
        this.cost = cost;
        this.person = person;
    }
}

 

😄결과

간단한 dp문제여서 쉽게 진행했던 것 같다.