[BOJ 2293,2294] 동전 1,2

https://www.acmicpc.net/problem/2293

https://www.acmicpc.net/problem/2294

각각 동전 1, 동전 2 의 문제이다. n종류의 동전을 이용하여 m이라는 값을 만드는 문제였다. 

처음에 접근했을때는 dp는 dp인데 2차원으로 dp[i][j] 를 i번째 숫자까지 이용해서 j를 만드는 방법으로 접근을 했는데 하다가 계속 삽질을 한....

간단하게 접근해보면 1차원 dp로도 문제를 해결할 수 있다.  

이렇게 기록하는 이유는 이러한 문제를 1차원으로도 2차원 dp느낌을 낼 수 있어서이다.

동전 1의 경우 점화식을 dp[j]를 j값을 만드는데 가능한 경우의 수 로 두고 식을 세우면 dp[j] +=dp[j-arr[i]] ( arr[i] = i번째 숫자 ) 라고 할 수 있다.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,arr[11111],dp[11111];
string s;
 
int main(){
    scanf("%d%d" , &n,&m);
    
    for(int i=1;i<=n;i++){
        scanf("%d" , &arr[i]);
    }
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(j-arr[i]>=0){
                dp[j] += dp[j-arr[i]];
            }
        }
    }
    printf("%d\n" , dp[m] );
}

이런식으로 해결할 수 있다.