문제

쉽게 생각했다가 큰 코 다쳤다…

문제 링크

문제 접근

  • 동전을 이용해서 만들 수 있는 수의 가지수를 dp에 담으면 되는 문제이다.
  • 여기서 문제는 중복이 안된다는 것이다.
  • 어떻게 중복을 해결 할 수 있을까?

중복 방지 dp

  • 중복을 해결하기 위해서는 하나의 동전으로 만들 수 있는 모든 경우의 수를 끝내고 다음 동전의 경우의 수를 추가하면 된다.
  • 중복이 가능하다면 dp[i]에 왔을 때 각 동전의 값을 뺀 위치의 값을 더해주면 된다.
  • 하지만 중복이 안될 때는 각 동전으로 dp값을 쭈욱 최신화하고 다음 동전을 넣고 다시 최신화 하기를 반복해줘야 한다.
  • 이렇게 되면 동전이 1, 2일 때, 1의 반복이 끝나면, {1}, {1, 1}, {1, 1, 1}, … 이 만들어지고 2의 반복이 끝나게 되면
  • {1}, {1, 1}, {2}, {1, 1, 1}, {1, 2}, {1, 1, 1, 1}, {1, 1, 2}, {2, 2}… 이런 식으로 만들어지게 되서 중복을 방지 할 수 있다.

코드

#include <cstdio>
int x, y, n, m, k, dp[16][16];
int main(){
    scanf("%d %d %d", &n, &m, &k);     
    dp[0][0] = 1; 
    x = (k - 1) / m, y = (k - 1) - x * m;
    if(k != 0){
        for(int i = 0; i <= x; i++){
            for(int j = 0; j <= y; j++){
                if(i + 1 <= x)dp[i + 1][j] += dp[i][j];
                if(j + 1 <= y)dp[i][j + 1] += dp[i][j];
            }
        }
    }
    else x = 0, y = 0;
    for(int i = x; i < n; i++){
        for(int j = y; j < m; j++){
            if(i + 1 < n)dp[i + 1][j] += dp[i][j];
            if(j + 1 < m)dp[i][j + 1] += dp[i][j];
        }
    }
    printf("%d", dp[n - 1][m - 1]);
}

느낀점

  • 중복의 문제에 항상 긴장했는데 이번 기회로 다른 문제도 뚫을 수 있을 것 같다.