백준 / 2293 / 동전 1 / java

package backjun.M동적계획2;

import java.util.Scanner;

public class 동전 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] coin = new int[n];
        int[] dp = new int[k+1];

        for(int i=0; i<n;i++){
            coin[i] = sc.nextInt();
        }
        sc.close();

        for(int i=0;i<n;i++){
            for(int j=1; j<=k; j++){
                if(j == coin[i])
                    dp[j] += 1;
                else if(j > coin[i])
                    dp[j] = dp[j-coin[i]] + dp[j]; 
                
            }
        }   
        System.out.println(dp[k]);
    }
}

냅색을 통해 해결하는 문제지만 메모리를 고려해야하는 문제

메모리가 4MB로 매무 적게 주어지기 때문에 냅색처럼 2차원 배열로는 문제를 해결할 수 없다.

그렇기 때문에 1차원 배열로 해결해야한다.

이 문제의 경우 주어진 숫자보다 낮은 경우는 이전 dp 정보를 그대로 가지고 있고 같은 경우는 이전 정보 + 1 해주면 되며 마지막으로 큰 경우는 해당 숫자만큼 뺀 dp의 인덱스 값을 이전 정보에 더해주면된다.
즉 모든 경우가 이전 정보를 포함하고 있다. 그렇기 때문에 2차원 배열이 아닌 1차원 배열로 구현이 가능하다.