[백준] 2294 동전2

문제보기

DP - Bottom Up

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

public class Main{
  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
   	int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
		
    // 동전 종류를 입력받음
    int[] c = new int[n];
    for(int i = 0 ; i < n ; i++){
      c[i] = Integer.parseInt(br.readLine());
    }
		
    // 가치에 따른 최소 동전 갯수를 저장할 변수
    long[] d = new long[k+1];
		
    // 초기화
    for(int i = 0 ; i < n ; i++ ){
      // 만약 동전값이 k값보다 작으면
      if(c[i] < k){
        // 해당 값까지 가는 최소 갯수는 늘 1개이다
        d[c[i]] = 1;    
      }
      // 만약 동전값이 k값과 같다면
      if(c[i] == k){
        // 말해 뭐해 그거 하나내면 최손데..
        System.out.println(1);
        return;
      }
    }
		
    // DP - Bottom Up
    // i - 동전 가치의 합, l - 동전 순서대로 iteration
    for(int i = 1 ; i <= k ; i++ ){
      for(int l = 0 ; l < n ; l++ ){
        // 목표 가치가 동전 1개의 가치보단 커야함 & 그 동전이 없을 때의 가능한 경우가 적어도 하나는 있어야함 
        if( i - c[l] >= 0 && d[i-c[l]] != 0 ){
          // 아직 d[i]에 저장된게 없다면 고스란히 담아주기 
          // c[i] 가 1개 추가되는것이므로 +1
          if( d[i] == 0 ){
            d[i] = d[i-c[l]]+1;
          }else{
            // 그게 아니면 이제 나 자신과의 싸움... 최소를 잡아야 한다
            d[i] = Math.min(d[i], d[i-c[l]]+1);
          }
        }
      }
    }

    if(d[k] != 0){
      System.out.println(d[k]);
      return;
    }
    System.out.println(-1);
  }
}

아 심지어 나는 Bottom up도 잘 못하는구나 ㅠㅠ 반성한 문제…