공부흔적

문제 링크

풀이 ) DP

  이항 계수 공식을 이용한 풀이이다.

  _nC_k = 1 ( k = 0 or k = n ), _n-1C_k-1 + _n-1C_k ( 0 < k < n )

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1002][1002];

int main(void)
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= i && j <= k; ++j){
            if(j == 0 || j == i)
                memo[i][j] = 1;
            else
                memo[i][j] = (memo[i-1][j-1]+memo[i-1][j]) % 10007;
        }
    printf("%d\n", memo[n][k]);
    return 0;
}

주의점 )

  - k = 0, k = n일 때 1로 처리

  - 모듈러 연산

문제 링크

풀이 ) DP

  동전의 순서가 답에 영향을 미칠 수 있기 때문에 각 동전에 따라 반복문을 돌린다.

  첫 번째 동전으로 만들 수 있는 k 이하의 금액을 확인하고 그다음 두 번째 동전까지 사용했을 때 만들 수 있는 금액을 확인하고 하는 방식으로 구현을 했다.

  처음 구현했을 때 //check 부분에서 memo[coin[i]]++; 을 했었는데 그렇게 되면 예제 입력을 실행할 경우 첫 번째 동전으로 만드는 금액에서 2, 3번째 동전을 사용한 경우가 추가로 더해지기 때문에 정답이 나오지 않았다.

  입력 예제의 경우 i = 0일 때 memo[j]가 모두 1이 되어야하는데 memo[2]가 2가 되어서 다른 숫자에 영향을 미치게 된다.

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[100002];

int main(void)
{
  int n, k, coin[102] = {0, };
  scanf("%d%d", &n, &k);
  for(int i = 0; i < n; ++i)
    scanf("%d", coin+i);
    // check

  for(int i = 0; i < n; ++i){
    memo[coin[i]]++;
    for(int j = 1; j <= k; ++j)
      if(j > coin[i])
        memo[j] += memo[j-coin[i]];
  }

  printf("%d\n", memo[k]);
  return 0;
}

주의점 )

  바깥 for문을 k번 반복하고, 안쪽 for문을 n번 반복하게 구현한다면 순서를 바꿨을 때 중복이 생기는 경우가 있어서 오답이 나온다.

  3원을 만들 때 1원+2원과 2원+1원이 각각 다른 경우로 분류된다.

문제 링크

풀이 ) DP

  각 숫자는 0부터 9의 숫자로 끝날 수 있다.

  또 m으로 끝나는 n자리 숫자는  m이하의 0 ~ m의 숫자로 끝나는 n-1자리 숫자 + m의 구조로 이루어져 있다.

  따라서 점화식은 memo[n][m] = ∑memo[n-1][i] (i = 0~m)이다.

  이 때 ∑memo[n-1][i] (i = 0~m-1) = memo[n][m-1]이므로 식을 다시 정리하면 다음과 같다.

  memo[n][m] = memo[n][m-1] + memo[n-1][m]

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1002][10] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

int main(void)
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i < n; ++i){
        memo[i][0] = memo[i-1][0];
        for(int j = 1; j < 10; ++j)
            memo[i][j] = (memo[i-1][j] + memo[i][j-1]) % 10007;
    }
    for(int i = 0; i < 10; ++i)
        ans += memo[n-1][i];
    printf("%d\n", ans % 10007);
    return 0;
}

주의점)

  - for문 내에서 모듈러 연산을 해주어 정수 오버플로우가 발생하지 않도록 한다.

  - memo[i][0]은 안쪽 for문에서 빼주어 런타임 에러를 방지한다.

문제 링크

풀이 ) DP

  각 숫자는 0을 제외한 1부터 9까지의 숫자로 끝날 수 있다.

  0으로 끝나는 n자리 숫자는 1로 끝나는 n-1자리 숫자 + 0의 구조이고

  1로 끝나는 n자리 숫자는 0 또는 2로 끝나는 n-1자리 숫자 + 1의 구조이다.

  같은 방식으로 m으로 끝나는 n자리 숫자는 m-1 또는 m+1로 끝나는 n-1자리 숫자  + m이고

  마지막 9로 끝나는 경우 앞이 8로 끝나는 숫자 + 9의 구조이다.

  따라서 점화식은 다음과 같다.

  memo[i][j] = memo[i-1][1] ( j = 0 ), memo[i-1][j-1] + memo[i-1][j+1] ( 0 < j < 9 ), memo[i][8] ( j = 9 )

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[102][10] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, };

int main(void)
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i < n; ++i){
        memo[i][0] = memo[i-1][1];
        for(int j = 1; j < 9; ++j)
            memo[i][j] = (memo[i-1][j-1]+memo[i-1][j+1]) % 1000000000;
        memo[i][9] = memo[i-1][8];
    }
    for(int i = 0; i < 10; ++i)
        ans = (ans + memo[n-1][i]) % 1000000000;
    printf("%d\n", ans);
    return 0;
}

문제 링크

풀이 ) DP

  초기화를 할 때 입력되는 카드로 바로 초기화를 한 후 이후

  n개의 카드를 n-m개, m개의 카드 두 부분으로 나누어서 n-m의 카드로 이루어진 최댓값에 m개가 포함된 카드팩의 합의 최대를 구한다.

#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
    int n, card[1001], memo[1001] = {0, };
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", card+i);
        memo[i] = card[i];
    }
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            memo[i] = max(memo[i], memo[i-j]+card[j]);
    printf("%d\n", memo[n]);
    return 0;
}

문제 링크

풀이 ) DP

  이 문제를 풀 때 memo[i]에 대해서 초기화를 할 때는 i 를 i-1과 1로 나눌 수 있으므로 memo[i-1] + 1로 한다.

  이후 2의 제곱인 4부터 시작해서 i에서 뺀 memo[i - j^2] + 1과 현재의 memo[i]를 비교하여 작은 값을 memo[i]에 저장한다.

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[100002] = {0, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i){
        memo[i] = memo[i-1]+1;
        for(int j = 2; j*j <= i; ++j)
            memo[i] = min(memo[i], memo[i-j*j]+1);
    }
    printf("%d\n", memo[n]);
    return 0;
}