백준 1106번: 호텔

문제 설명

• https://www.acmicpc.net/problem/1106
• A원을 들이면 B명의 고객을 늘릴 수 있다는 정보가 주어집니다. 이때 적어도 C명의 고객을 얻기 위해 최소한으로 얼마의 돈을 쓰는지 구하는 문제입니다.

접근법

• 핵심은 '적어도' C명입니다.
• 지금까지 대부분 dp[i]를 사람 i명을 모으는 최소비용으로 정의했습니다. 하지만 이 문제는 적어도라는 조건 때문에 예상과 다른 결과가 나타납니다.
• 예제 2번을 살펴봅시다. [0,3,2,1,4,3,2,5,4,3,6,5,4]
  만약 정확히 10명을 모으는 최소비용이었다면 6원을 소모해야 합니다. 하지만 해당 예제는 11명을 모으는 비용이 5원, 12명을 모으는 비용이 4원으로 더 좋은 조건이 존재하고, 해당 문제에서는 12명을 모으는 4원이 최소비용이 됩니다.
• 그래서 dp[i]를 dp[i]를 사람 i명을 모으는 최소비용이 아니라 dp[i]를 적어도 사람 i명을 모으는 최소비용으로 정의해야 합니다.
  3명을 모으는 비용이 1원일 때 단순 최소비용은 dp[i] = Math.min(dp[i],dp[i-3]+1)이지만 적어도를 반영한 최소비용은 dp[i] = Math.min(dp[i],dp[i-3]+1,dp[i-2]+1,dp[i-1]+1)가 됩니다.
  • dp[i-3]+1: 해당 조건으로 i명을 모으는 비용
  • dp[i-2]+1: 해당 조건으로 i+1명을 모으는 비용
  • dp[i-1]+1: 해당 조건으로 i+2명을 모으는 비용

정답

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

public class Main {
	public static void main(String[] args) throws Exception {
		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+1]; // dp[i] = 최소 i명을 대려오는데 드는 비용 
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		List<Info> lst = new ArrayList<Info>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int cost = Integer.parseInt(st.nextToken());
			int person = Integer.parseInt(st.nextToken());
			lst.add(new Info(cost, person));
		}
		
		for (int i = 1; i < dp.length; i++) {
			for (int j = 0; j < lst.size(); j++) {
				Info now = lst.get(j); // 현재 도시의 정보
				for (int k = i-now.person; k <= i; k++) {
					if(k<0) continue;
					dp[i] = Math.min(dp[i], dp[k]+now.cost);
				}
			}
		}
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[C]);
		
	}

	public static class Info {
		int cost;
		int person;

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

		@Override
		public String toString() {
			return "Info [cost=" + cost + ", person=" + person + "]";
		}

	}

}