oiehso0

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

풀이

2행 n열로 구성되어있는 스티커이기 때문에 2차원 배열을 이용해서 dp로 구하기로 한다.

dp[i][j] 는 arr[i][j]까지의 스티커 배열 중에 스티커를 골라 최대값이 나올 수 있게 골라 더한 값을 담는다고 하자.

i)

arr[1][1]    arr[1][2]   arr[1][3]    arr[1][4]    arr[1][5]

arr[2][1]   arr[2][2]    arr[2][3]    arr[2][4]    arr[2][5]            ===>    dp[1][4] = dp[2][2] + arr[1][4];

dp[2][4] = max(dp[1][2] + arr[2][4] , dp[1][3] + arr[2][4]); 

위와 같은 방법으로 모든 스티커에 대해 dp를 구해 나가고 마지막 배열 dp[1][N], dp[2][N] 두가지 값만 비교해서 최대값을 출력해주면 된다.

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

풀이

n가지 종류의 서로 다른 값의 동전을 주고 각 동전들을 적당히 사용해서, 그 가치의 합이  k원이 되도록 할 때 총 경우의 수를 구하는 문제이다. 

각각의 동전은 몇개라도 사용해서 k원을 만들면 된다.

예를 들어서 coin[1] = 1, coin[2] = 2, coin[3] = 5 의 3가지 동전이 주어졌고 10을 만드는 총 경우의 수를 구해야 한다고 하면

먼저 1을 만들 수 있는 경우의 수부터 2를 만들 수 있는 경우 , 3, 4, .... 이런식으로 dp[j]에 coin[i] 순서대로 구해 저장 해놓기로 한다.

int dp[10001] = { 0 }; 

dp[0] = 1;

1을 만들 수 있는 경우 1  (1 가지) 1. dp[1] = dp[1] + dp[1 - coin[1]];

2를 만들 수 있는 경우 (1)-1 / 2 ( 1 + 1 가지) 2. dp[2] = dp[2] + dp[2 - coin[1]];     /   6.  dp[2] = dp[2] + dp[2 - coin[2]];

3을 만들 수 있는 경우 (1-1)-1 / (1)-2 (1 + 1 가지) 3. dp[3] = dp[3] + dp[3 - coin[1]];    /  7.  dp[3] = dp[3] + dp[3 - coin[2]];

4를 만들 수 있는 경우 (1-1-1)-1 / (1-1)-2 / (2)-2 (1 + 2 가지) 4. dp[4] = dp[4] + dp[4 - coin[1]];    /    8. dp[4] = dp[4] + dp[4 - coin[2]];

5를 만들 수 있는 경우 (1-1-1-1)-1 / (1-1-1)-2 / (1-2)-2 / 5 (1 + 2 + 1 가지) 5. dp[5] = dp[5] + dp[5 - coin[1]];    /    9. dp[5] = dp[5] + dp[5 -coin[2]];    /    10. dp[5] = dp[5] + dp[5 - coin[3]] ;

.

.

.

이런 식으로  순차적으로 dp를 구해주면 된다.

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

풀이

i개의 서쪽 사이트와 j개의 동쪽 사이트를 잇는 다리를 지을 수 있는 경우의 수 dp[i][j]라고 하자.

dp[1][1]

dp[1][2]    dp[2][2]

dp[1][3]    dp[2][3]    dp[3][3]

dp[1][4]    dp[2][4]    dp[3][4]    dp[4][4]

.

.

.

이런식으로 dp[N][M]까지의 dp를 모두 구할 것이다.

이해하기 쉽게 예를 들어보기로 한다.

ex) 사이트에 번호를 메기고 dp[2][4]의 다리를 놓는 경우의 수를 알고싶다. 

1과 2의 경우로 나누어 생각해보자 

1번의 경우

먼저 그림의 1번 경우와 같이 2-4를 잇게 되면 N-1 개의 사이트와 M-1개의 사이트를 잇는 경우의 수를 구하는 꼴이 된다.

 즉, dp[1][3]의 값이라고 할 수 있다.

2번의 경우

다음은 그림의 2번 경우와 같이 2-3을 잇게되면 N개의 사이트와 M-1개의 사이트를 잇는 경우의 수를 구하는 꼴이 된다.

즉, dp[2][3]의 값이라고 할 수 있다.

dp[N][M] = dp[N-1][M-1] + dp[N][M-1];

위처럼 모든 dp에 성립하는 식이 만들어지게 된다.