[구름톤 챌린지] 통증 (2)

풀이 과정

먼저, 이 문제는 Dynamic Programming으로 해결할 수 있다. 예를 들어, 3, 4, 5 힐 아이템이 있다고 가정하고, 9라는 통증을 0으로 만들어야하는 상황을 가정해보자. 그 때, 3원의 동전으로 통증 3을 해결하는 방법은 1가지이고, 통증 6을 해결하는 방법은 통증 (6 - 3)을 해결하는  경우의 수 + 1 즉, 2가 된다. 그리고 마지막 통증 9를 해결하기 위해서는 통증 (9 - 3)을 해결하는 방법 + 1이 된다. 다시 4원과 5원을 봤을때 통증 4를 해결하는 방법, 통증 5를 해결하는 방법은 각각 1가지가 되고, 통증 9를 해결하는 방법은 통증 (9 - 4)를 해결하는 방법 + 1(본인) 즉, 2가지가 필요하다. 따라서 정답은 2가 된다. 이를 순서대로 다시 작성해보자.

1. dp 배열을 N + 1만큼 크기를 잡는다.(우리가 원하는 통증은 인덱스 N에 있기 때문)
2. 첫 번째 인덱스 0을 만다는데 필요한 경우의 수(0)를 첫 번째 값에 초기화한다.
3. dp 배열의 2번째 인덱스부터 돌면서 해당 인덱스를 amount + 1으로 잡는다.(amount + 1보다는 필요한 개수가 적기 때문)
4. 해당 통증(인덱스의 값)이 힐 아이템보다 크면 (통증 - 해당 힐 값)의 필요한 개수 + 1를 구하고 현재 통증에 있는 인덱스 값과 비교한다.
5. 더 적게 아이템이 필요하면 해당 아이템 개수로 대체한다.
6. 이 과정을 해당 통증 인덱스까지 올때까지 반복한다.
7. 만약 아이템들을 가지고 통증을 0으로 만들지 못하면 -1, 0을 만들었다면 해당 필요한 개수를 반환한다.

 

코드

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] healItems =  Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int[] dp = new int[N + 1];
	
		dp[0] = 0; // 0이 되는 경우의 수는 0
		
		for (int i = 1; i <= N; i++) {
			dp[i] = N + 1;
			for (int heal : healItems) {
				if (i >= heal) {
					dp[i] = Math.min(dp[i], dp[i - heal] + 1);
				}
			}
		}
		
		System.out.println(dp[N] > N ? -1 : dp[N]);
	}
}