[다이나믹]-문제2

1. 막대기

2. 합분해

3. 폐지줍기

4. 동전2

5. 돌다리 건너기

6. 바둑돌 잇기

---------------------------- 

1. 막대기

n가지 종류의 막대기가 있다. 막대기의 길이는 모두 다르다. 이 막대기들을 적당히 사용해서, 총 길이가 K가 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 막대기는 여러번 사용할 수 있다.)

입력

첫째 줄에 n,k 가 주어진다. (1 <= n <= 100, 1 <= k <= 10,000) 다음 n개의 줄에는 각각의 막대기의 길이가 주어진다.

출력

첫째 줄에 경우의 수를 출력한다. 1000000으로 나눈 나머지를 출력하시오.

풀이

- n개가 아닌, n종류라는 데 주의. 즉, 1종류를 여러번 사용 가능

- D[i][j]: i개까지의 막대기를 이용해서, j 길이 만큼을 만들 수 있는 경우의 수

- D[0][0]=1  ==> 0개의 막대기를 이용해서 길이 0만큼 만들 수 있는 경우의 수

  D[i][j] = Sum(D[i-1][j - k x s[i]), 0 <= k <= j/s[i]

  ==> i개까지 막대기를 사용해서 j길이만큼을 만들 수 있는 경우의 수는, 

  한 개 덜 사용하면서(i-1개 사용하면서), i번째 막대기를 0번사용~j/s[i]번까지 사용할 때의 경우의 수를 모두 합한 것.

  즉, i번째 막대기를 안 사용할 수도 있고, 1개 사용할 수도 2개 사용할 수도 있는 것. 

  최대 몇개까지 사용할 수 있는 가는, j - k x s[i] > 0 이므로,  k <= j/s[i] 일 때까지.

소스

#include <stdio.h>

 

int N, K;

int s[101];

int D[101][10001];

int MOD = 1000000;

int solve() {

         D[0][0] = 1;

 

         for (int i = 1; i <= N; ++i) {

                  for (int j = 0; j <= K; ++j) {

                           for (int k = (j / s[i]); k >= 0; --k) {

                                   D[i][j] += D[i - 1][j - k*s[i]];

                                   if (D[i][j] >= MOD) {

                                            D[i][j] -= MOD;

                                   }

                           }

                  }

         }

 

         return D[N][K];

}

 

int main()

{

         //freopen("stick.txt", "r", stdin);

         setbuf(stdout, NULL);

 

         scanf("%d%d", &N, &K);

 

         for (int i = 1; i <= N; ++i) {

                  scanf("%d", &s[i]);

         }

 

         int ans = solve();

         printf("%d", ans);

 

         return 0;

}

2. 합분해

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1≤N≤200), K(1≤K≤200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이

- D[K][N]을 구하는 것. 숫자를 K개 더해서 그 합이 N이 되는 경우의 수

- D[i][j]: 숫자를 i개 더해서, 그 합이 j가 되는 경우의 수

- D[i][j] = D[i-1][j] + D[i-1][j-1] + ... +D[i-1][0]  

           = Sum(D[i-1][k], 1<=i<=K, 0<=j<=N, 0<=k<=j    ;j가 0부터 시작함에 유의. 합이 0이되는 경우 있음

   ==> i개 더해서 합이 j가 되는 경우의 수는, i-1개 사용해서 j가 된 후 0을 더하거나(i번째 수로 0을 선택), i-1개 사용해서 합이 j-1인 상태에서 i번째로 1을 사용하거나,  j-2에서 2를 사용하는 등의 조합이 가능(수는 0~j까지 존재하니깐)

- D[0][0]=1 ==> 숫자 0개를 더해서 그 합이 0이되는 경우의 수는 1

소스

#include <stdio.h>

 

int N, K;

 

int D[203][203];

 

int main() {

         scanf("%d %d", &N, &K);

 

         D[0][0] = 1;

         for (int i = 1; i <= K; i++) {

                  for (int j = 0; j <= N; j++) {

                           for (int k = 0; k <= j; k++) {

                                   D[i][j] += D[i - 1][k];

                                   D[i][j] %= 1000000000;

                           }

                  }

         }

 

         printf("%d\n", D[K][N]);

 

         return 0;

}

3. 폐지줍기

N * N 격자로 이루어진 도시가 있다. 이 도시 군데군데에는 폐지가 버려져 있다.

범수는 가장 왼쪽 위 격자 (1,1)에서 출발하여 가장 오른쪽 아래 격자 (N,N)까지 이동하며 폐지를 줍는데, 최단 경로를 따라가야만 한다. 즉, 인접한 오른쪽 칸 또는 아래쪽 칸으로만 이동할 수 있다. 이 때, 범수가 수집할 수 있는 폐지의 최대값을 출력하시오.

출발점과 도착점에 위치한 폐지 또한 주울 수 있다.

시간제한: 1초

입력

첫 줄에는 도시의 크기 N(2 ≤ N ≤ 200)이 주어진다. 그 다음 N개의 줄에 도시의 정보가 주어진다. 도시의 정보 중 i번째 줄의 j번째 숫자는 격자 (i, j)에 버려진 폐지의 양 A_ij을 나타낸다. (0 ≤ A_ij ≤ 1000)

출력

범수가 주울 수 있는 최대 폐지 양을 출력한다.

풀이

- D[i][j] : (i,j)칸에서의 폐지 최대값

  D[1][1] = a[1][1]

  D[i][j] = max(D[i][j-1], D[i-1][j]) + a[i][j]

  ==> a[i][j] += max(a[i][j-1], a[i-1][j] 로도 가능

소스

#include <stdio.h>

#include <algorithm>

 

using namespace std;

 

int n, p[210][210];

 

int main(){

         scanf("%d", &n);

         for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)scanf("%d", p[i] + j);

         for (int i = 1; i <= n; i++){

                  for (int j = 1; j <= n; j++){

                           p[i][j] += max(p[i - 1][j], p[i][j - 1]);

                  }

         }

         printf("%d", p[n][n]);

         return 0;

}

4. 동전2 - 백준 2294번

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)

입력

첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 100,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

출력

첫째줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제입력

3 15

1

5

12

예제 출력

3

핵심

- D[i]: i 금액을 만들 수 있는 최소 동전 갯수 -> D[k]=?

- 먼저, 동전 한 종류로 만들 수 있는 D[i]값들을 구한다. 

  예를 들어 2원, 3원짜리 동전이 있다면,

  D[2*1] = 1, D[2*2]=2, D[2*3]=3,..

  D[3*1] = 1, D[3*2]=2, D[3*3]=3

  ==> 값을 갱신할 때, 기존값과 비교해서 작은 경우만 갱신

- 동전 한 종류로 만들 수 있는 최소D[i]들을 구했으니, 이제 동전 여러개의 조합을 이용해서의 D[i]값을 구할 수 있음

  i는 2~k까지, j는 1~(i/2)까지 변화시키면서. (j=0인경우, 검사 할 필요 없음)

  D[i] =  (D[i]==-1) ? D[j]+D[i-j] : min(D[i],D[j]+D[i-j], 2<=i<=k, 1<=j<=(i/2)

소스

#include <stdio.h>

#include <limits.h>

#include <algorithm>

 

#define MAX 103

using namespace std;

 

int n,k;

int p[MAX];

int D[MAX][100003];

/*

p[i]: i번째 동전 가치

D[i][j]: i번째 동전까지 사용해서, 금액j를 만들 수 있는, 최소동전갯수. 1<=i<=n, 0<=j<=k

D[n][k]=?

D[0][0]=0, D[1][0]=0, D[1][p[i]]=1

 

D[i][j] = min(D[i-1][j] + 0 , D[i-1][j-p[i]] + 1,...)

= min(D[i-1][j-t*p[i]] + t), 0<=t<=(j/p[i])

 

*/

int main() {

         scanf("%d %d", &n,&k);

         for (int i = 1; i <= n; ++i)        scanf("%d", &p[i]);

        

        

         for (int i = 0; i <= n; ++i)  for (int j = 0; j <= k; ++j)             D[i][j] = -1;

         D[0][0] = 0;

         for (int i = 1; i <= n; ++i) {

                  for (int j = 0; j <= k; ++j) {

                           D[i][j] = INT_MAX;

                           for (int t = 0; t <= (j / p[i]); ++t) {

                                   int idx = j-t*p[i];

                                   if (D[i - 1][idx] != -1) D[i][j] = min(D[i][j], D[i-1][idx]+t);

                           }

                  }                

         }

         if (D[n][k] == INT_MAX) D[n][k] = -1;

         printf("%d\n", D[n][k]);

         return 0;

}

5. 돌다리 건너기

절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 <악마의 돌다리>이로 다른 하나는 <천사의 돌다리>이다.

아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 <악마의 돌다리>를 표시하는 것이고, 아래의 가로줄은 <천사의 돌다리>를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다.

출발 R I N G S R 도착

 G  R  G  G  N  S

 

반지원정대가 소유하고 있는 마법의 두루마리에 <악마의 돌다리>와 <천사의 돌다리>를 건너갈 때 반드시 순서대로 밟고 지나가야할 문자들이 적혀있다. 이 순서대로 지나가지 않으면 돌다리는 무너져 반지원정대는 화산 속으로 떨어지게 된다.

다리를 건널 때 다음의 제한 조건을 모두 만족하면서 건어야 한다.

1) 왼쪽(출발지역)에서 오른쪽(도착지역)으로 다리를 지나가야 하며, 반드시 마법의 두루마리에 적힌 문자열의 순서대로 모두 밟고 지나가야 한다.

2) 반드시 <악마의 돌다리>와 <천사의 돌다리>를 번갈아가면서 돌을 밟아야 한다. 단, 출발은 어떤 돌다리에서 시작해도 된다.

3) 반드시 한 칸 이상 오른쪽으로 전진해야하며, 건너뛰는 칸의 수에는 상관이 없다. 만일 돌다리의 모양이 그림 1고 같고 두루마리의 문자열이 "RGS"라면 돌다리를 건너갈 수 있는 경우는 다음의 3가지 뿐이다. (아래 그림에서 빨간색 문자는 밟고 지나가는 돌다리를 나타낸다.)

출발 R I N G S R 도착

 G  R  G  G  N  S

출발 R I N G S R 도착

 G  R  G  G  N  S

출발 R I N G S R 도착

 G  R  G     G  N  S

 

아래의 세 방법은 실패한 방법이다.

출발 R I N G S R 도착

 G  R  G     G    N  S

출발 R I N G S R 도착

 G  R  G  G  N  S

출발 R I N G S R 도착

 G  R  G  G  N  S

왜냐하면 첫 번째는 문자열 "RGS"를 모두 밟고 지나가야 하는 조건 1)을 만족하지 않으면, 두 번째는 번갈아가면서 돌을 밟아야 하는 조건 2)를, 세 번째는 앞으로 전진을 하여야하는 조건 3)을 만족하지 않기 때문이다.

마법의 두루마리에 적힌 문자열과 두 다리의 돌에 새겨진 문자열이 주어졌을 때, 돌다리를 통과할 수 있는 모든 가능한 방법의 수를 계산하는 프로그램을 작성하시오. 예를 들어, 그림 1의 경우는 통과하는 방법이 3가지가 있으므로 3을 출력해야 한다.

입력

첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 <악마의 돌다리>와 <천사의 돌다리>를 나타내는 같은 길이의 문자열이 주어진다. 그 길이는 1 이상, 100 이하이다.

출력

마법의 두루마리에 적힌 문자열의 순서대로 다리를 건너갈 수 있는 방법의 수를 출력한다. 그러한 방법이 없으면 0을 출력한다.

모든 테스트 데이터에 대한 출력결과는 231-1 이하이다.

예제 입력  

RGS

RINGSR

GRGGNS

예제 출력  

3

풀이

Tn = 목표 문자열

Am : 천사 돌다리

Bm : 악마 돌다리

D[i][j][0] : 천사돌다리로 끝나면서, i번째 목표문자열까지, j번째 돌다리문자를 이용해서 만들 수 있는 최대 경우 수

D[i][j][1] : 악마돌다리로 끝나면서, ...

 

if(T[i] == A[j]) //목표문자열 i번째와 천사돌다리 j번째가 같다면

D[i][j][0] = Sum(D[i-1][k][1]), 0<= k <= j-1  // (j-1)까지의 악마돌다리에서의 경우의 수 합

if(T[i] == B[j]) //목표문자열 i번째와 악마돌다리 j번째가 같다면

D[i][j][1] = Sum(D[i-1][k][0]), 0<= k <= j-1  // (j-1)까지의 천사돌다리에서의 경우의 수 합

 

D[0][0][0] = D[0][0][1] = 1

  //0번째 목표문자열, 0번째 돌다리문자 이용 경우의 수로, 1의 의미가 좀 약하지만,

 //이렇게 해야 위의 점화식의 Sum값이 제대로 동작

 

ans = Sum(D[n][k][0] + D[n][k][1]), 1<= k <=m  //모두 더해줌에 유의. 달랑 D[n][m][0] + D[n][m][1] 이 아님

 //돌다리의 끝까지인 m까지 사용안하고도, 목표문자열을 만족시킬 수 있기 때문

소스

#include <stdio.h>

#include <string.h>

char T[23],A[103],B[103];

int D[23][103][2];

int main() {

    int i, j, k;

    int n,m;

    scanf("%s", &T[1]);

    scanf("%s %s", &A[1],&B[1]);

    n = strlen(&T[1]);

    m = strlen(&A[1]);

 

    int sum = 0;

    D[0][0][0] = D[0][0][1] = 1;

    for (i = 1; i <= n; ++i) {

        for (j = 1; j <= m; ++j) {

            if (T[i] == A[j]) for (k = 0; k <= (j - 1); ++k) D[i][j][0] += D[i-1][k][1];

            if (T[i] == B[j]) for (k = 0; k <= (j - 1); ++k) D[i][j][1] += D[i-1][k][0];        

        }

    }

    int ans=0;

    for (j = 1; j <= m; ++j) ans += (D[n][j][0] + D[n][j][1]);

    printf("%d\n", ans);

    return 0;

}




6. 바둑돌 잇기

-끝-