[C] 2293: 동전 1

시간이 엄청 오래걸려서 풀었다..

일단 맨 처음에는 재귀함수를 이용한 Top-Down 방식으로 풀려고 노력했는데 예외처리를 해줘도 지수적으로 증가하기 때문에 자꾸 시간초과가 났다.

 

여기서 주의해야할 점은 각각의 코인의 가치에 따라서 dp를 따로 생각해야한다는 점이다. 결국 마지막에는 하나로 모아 풀어야하지만 처음에 생각은 따로따로 해야한다는 점인데 그 결과 구현을 하자면

dp[i]+=dp[i-price[j]]; 가 된다

 

1. j번째 동전을 포함하지 않은 상태에서 i의 가치를 표현하기 위해서는 j-1번쨰 동전까지만을 이용하여 만들 수 있는 경우의 수를 구하면 되기 때문에 dp[i]+=dp[i]...가 된다.

2. j번째 동전을 포함한 상태라는 뜻은 결국 가치가 i-price[j]가 되는 경우의 수를 구하면 되기 때문에 j번째 동전도 포함상태이므로 dp[i]+=dp[i-price[j]] 가 된다 

 

다만 여기서 주의해야할 점은 동전의 가치가 구하고자하는 가치보다 클 수도 있기 때문에 이때 예외처리를 해야만 메모리초과가 일어나지 않을 수 있다.

if(i-price[j]>=0)
     dp[i]+=dp[i-price[j]];

 

dp문제를 많이 풀고 있지만 그래도 더 생각할게 많다. 위에서부터 재귀적으로 풀려고 노력할 때는 최적부분구조(지금까지 어떤 경로로 이 부분 문제에 도달했건 남은 부분문제는 항상 최적으로 풀어도 되는 문제)일때만 하는 것이 더 효율적일 것 같다.

 이 문제 같은 경우에는 순서가 달라도 구성이 같으면 같은 경우로 보았기 때문에 최적부분구조로 푸는 것이 힘들다.

그리고 항상 점화식을 먼저 찾기 위한 노력을 해야겠다!

 

참고로 밑에 사이트를 보면 이해하기 더 쉽다

https://seongjuk.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-2293%EB%B2%88-%EB%8F%99%EC%A0%84-1

[BOJ] 백준 2293번: 동전 1

 

밑에는 내 소스코드다!

#include <stdio.h>

int dp[10002];
int price[101];
int cases=0;

int main(void)
  {
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
      {
        scanf("%d",&price[i]); //올림차순으로 배열
      }

    dp[0]=1; //아무 동전도 선택하지 않은 경우
    for(int j=1;j<=n;j++)
      {
        for(int i=1;i<=k;i++)
          {
            if(i-price[j]>=0)
             dp[i]+=dp[i-price[j]]; //1.j번째 코인이 없는 상태에서 j-1번째 코인들만으로 되는 경우 (+dp[i])
            //2. j번째 코인이 있는 상태에서 생각하기 때문에 j번째 코인의 가치를 뺸 곳의 경우의 수를 더함
          }
      }
    
    
   printf("%d",dp[k]);
   
  }