oiehso0

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에 성립하는 식이 만들어지게 된다.

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

풀이

기존의 2xn타일링 문제에서 2x2타일이 추가된 형태이다.

기존 문제에서 2xn 크기의 직사각형을 1x2타일과 2x1타일을 이용해 채웠을때

dp[n] = dp[n-1] + dp[n-2]; 과 같은 식이 성립했다.

그 이유는 dp[n-1]까지의 타일 끝에 2x1의 타일을 이어 붙이는 경우 / dp[n-2]까지의 타일 끝에 1x2타일 두장을 이어 붙이는 경우를 더해 dp[n]의 타일의 경우의 수가 도출

되었기 때문이다. 

 <<< --- 타일링 2 문제에서는 n-2까지의 타일에 이어 붙이는 2x2 사각형의 경우가 1x2타일 2 개와 2x2타일 1 개를 이어 붙이는 경우로 나누어 지기 때문에

타일링 2 문제의 경우에서는

dp[n] = dp[n-1] + dp[n-2] * 2 ; 라는 식이 성립하게 된다. 

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

풀이

수열 중 가장 긴 증가하는 부분 수열을 구하면 된다.

arr[1] ... arr[n-1], arr[n]까지 총 n개의 수열이 주어진다고 할 때

dp[n] 을 이용해서 n번째 수열까지의 부분수열의 최대값을 저장하려고 한다.

1번째로 세워야할 조건

arr[n] > arr[n-1] 인가? 아니라면 증가하는 부분 수열이라고 할 수 없기 때문이다.

arr[i]를 마지막 배열이라고 가정 했을 때 수열의 최대 길이를 dp[i]라고 한다. 그러면  최대 dp[i]를 구하기 위해서 

arr[1], arr[2], arr[3] ... arr[i-1]까지 arr[i]보다 작은수가 존재하지 않는다면 dp[n]은 1이 될 것이다.

만약 arr[3]까지의 증가하는 부분수열의 최대길이인 dp[3]이 2라고 하고

arr[4]가 arr[3]의 값보다 크지 않다면 dp[4]는 2가 될것이다.

위의 조건과 예시를 종합해 조건식을 만들자면 아래와 같은 식이 나온다.

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

for(int j = 1; j < i; j++}{

if(arr[j]< arr[i]) dp[i] = dp[j] + 1;

}

}

하지만 빠진 조건이 하나 존재한다. 우리는 부분수열의 최대길이를 구해야하지만  위의 식대로 프로그램을 돌리면 위의 조건문을 만족하는 i 와 가장 가까운 j 의 부분수열의 최대길이가 dp[i]에 대입되기 때문에 아래 예시와 같은 예외의 경우가 나타나게 된다.

ex) 

2    3    4    1    5

    dp[i]    1    2    3    1    ? <<-- dp[5]는 4가 되어야 하지만 dp[5] = dp[4] + 1; 로 인해 2가 되어 버릴 것이다. 그래서 아래와 같은 조건 하나를 추가한다.

if(dp[i] < dp[j] + 1) dp[i] = dp[j] +1;

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

풀이

붕어빵이 N개 있다고 가정하자. 1개 팔 때의 가격(arr[1]), 2개 팔 때의 가격(arr[2]), .... N개 팔 때의 가격(arr[n])이 있을 것이다. N개의 붕어빵을 모두 팔 때 얻을 수 있는 최대 수익을 구해야 한다.

먼저 dp[1]은 N개의 붕어빵 중에 1개를 팔때 얻을 수 있는 최대 이익을 담는다고 하자.

그러면 dp[0] = 0; ,

 dp[1] = arr[1]; 이라고 할 수 있다.

다음으로 N개 중 2개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[2] = dp[1] + arr[1] or dp[0] + arr[2] 이다.

3개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[3] = dp[2] + arr[1] or dp[0] + arr[3] or dp[1] + arr[2] 이다.

4개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[4] = dp[3] + arr[1] or dp[0] + arr[4] or dp[2] + arr[2] or dp[1] + arr[3] 이다. 

dp[i] = max(dp[i-j] + arr[j]); 로 나타낼 수 있다.

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

풀이

                        1자리  2자리  3자리

뒷자리가 0일때 경우의 수   0개    1개    1개                 0뒤에 1

뒷자리가 1일때 경우의 수    1개    1개    3개                 1뒤에 0 이나 2

뒷자리가 2일때 경우의 수    1개    2개    3개                2뒤에 1 이나 3

뒷자리가 3일때 경우의 수    1개    2개    4개                3뒤에 2 나 4

뒷자리가 4일때 경우의 수    1개    2개    4개                4뒤에 3 이나 5

뒷자리가 5일때 경우의 수    1개    2개    4개                5뒤에 4 나 6

뒷자리가 6일때 경우의 수    1개    2개    4개                6뒤에 5 나 7

뒷자리가 7일때 경우의 수    1개    2개    4개                7뒤에 6 이나 8

뒷자리가 8일때 경우의 수    1개    2개    3개                8뒤에 7 이나 9

뒷자리가 9일때 경우의 수    1개    1개    2개                9뒤에 8

총 계단수            9        17     32    .  . .  .   .

위의 규칙에 따라 식을 만들게 되면 

dp[i][j] = dp[i - 1][j - 1] + dp[i  - 1][j + 1];    과 같은 식이 나오게 된다.

단 뒷자리가 0일 경우와 9일 경우는

dp[i][j] = dp[i - 1][j - 1] + dp[i  - 1][j + 1]; 의 식에서 파란 부분과 빨간 부분의 배열은 존재하지 않기 때문에 예외의 조건식을 작성해주면 된다.

그리고 1000000000으로 나눈 나머지를 출력하면되기 때문에  % 연산을 for문에 넣어준다.

자료형의 범위보다 훨씬 큰 값이 저장되지 않게 나머지를 출력하는 조건을 주어준 것이다.

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

풀이

연속된 수열이 있을때 이 중 연속된 몇개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제이다.

dp배열(기록해두는 배열)를 이용해서 수열 arr[1]부터 마지막 배열인 arr[n]까지 연산할 것이다.

먼저 arr[1]의 값을 dp[1]에 넣고 

if(dp[n-1] + arr[n] > arr[n]) 의 조건을 준다.

이전 dp(즉, arr[1]부터 arr[n-1] 까지의 합)가 0보다 큰 수라면 다음 배열 arr[n]도 더해서 다음 dp[n]에 저장하도록 한다.

하지만 만약 dp[n-1]이 0이거나 음수라면 과감하게 버려주고 dp[n]에 arr[n]만 넣어준다.

----->>

if(dp[n-1] + arr[n] > arr[n]) dp[n] = dp[n-1] + arr[n];

else dp[n] = arr[n];

위와 같은 식으로 알고리즘을 짜면 그때그때 수열의 합값을 dp에 기록하고 이전 dp가 0으로 접어들게 되면 이전 앞에서 부터 더해줬던 값들은 더할 의미가 사라지기 때문에 꼬리를 자르는 것처럼 버려준다. 그 대신 arr[n]값을 dp[n]에 넣어준다.(이 값이 dp[n]이 가질 수 있는 최대값) 이런식으로 배열 마지막까지 수행하게 되면 dp배열이 만들어 지게 되고

그리고 int Max; 를 만들어서 

Max = dp[1]

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

if(Max < dp[i]) Max = dp[i];

}

를 해주면 된다.

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

풀이

N잔의 포도주가 일렬로 놓여있다. 포도주 시식을 하는데 2가지 규칙이 존재한다.

1. 포도주 잔을 선택하면 모두 마셔야하고, 마신후에는 제자리에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.  ex) x o x o o o x 와 같은 경우는 불가하다.

위의 조건을 만족하면서 용량이 큰 포도주만 잘 골라마셔서 누적 최대 합을 만드는 알고리즘을 짜야한다. 

동적 계획법 알고리즘을 짤때 가장 핵심은 주어진 문제를 부분 문제로 나누어 생각해야하고 나눈 부분으로 전체 문제에서 나타날 수 있는 전체 경우의 수를 표현 할 수 있어야한다.

노트를 펴서 규칙을 나누고 생각해보면 3가지 부분으로 전체 문제를 쪼갤 수 있다. 

1. n번째 배열 arr[n]에서 arr[n-1]을 선택하여 마실경우

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 이라고 치면 arr[n-2]는 무조건 X(안마심)여야 한다.

arr[n-2]가 X라고 하면 arr[n-3]은 O or X 즉, 마실수도 안 마실 수 도 있지만 최대합을 구하는 문제에서 X(안마심)을 고를 필요는 없기 때문에 

arr[n-3]을 마시게 되고 최종적으로

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

O or X    /  O or X    /     O     /       X       /       O     /      O    /

dp[n] = dp[n-3] + arr[n-1] + arr[n]; 라는 식이 나오게 된다.

2. n번째 배열 arr[n]에서 arr[n-1]을 선택하지 않은 경우 

1번 경우와 마찬가지로 arr[n-1]을 선택하지 않으면 arr[n-2]는 무조건 마시는게 좋기 때문에

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

O  or  X  /  O or X  /  O or X   /       O      /     X        /     O    /

dp[n] = dp[n-2] + arr[n]; 과 같은 식이 나오게 된다.

3. n번째 배열을 arr[n]을 선택하지 않을 경우

arr[n]을 마시지 않으면 arr[n-1]은 선택하지 않아서 마시지 않을 이유가 없다.  그래서

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

 O or X  /   O  or  X /  O or X   /  O or X   /     O     /       X    /

dp[n] = dp[n-1]; 과 같은 식이 나오게 된다.

위의 세 경우를 종합하여 프로그래밍 하면 정답을 출력 할 수 있다.

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

풀이

계단을 차근차근 올라 마지막 계단(꼭 거쳐야하는 계단)까지 밟았던 계단의 합이 최대값이 나오게 하는 알고리즘을 짜야한다.

단 조건이 있는데

1. 계단은 한번에 1칸 or 2칸을 올라갈 수 있다.

2. 연속된 세 개의 계단을 모두 밟으면 안된다.

3. 마지막 도착 계단은 반드시 밟아야한다.

1, 2, 3의 조건을 모두 조합해서 최대합 dp를 구하는 식을 나타내보면

arr[1] arr [2]  /중략/  arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n]     <<- n개의 계단을 만들었다고 치면 계단 마지막 쯤은 이런식으로 생겼을 것이다. 

n의 계단을 꼭 밟는다는 조건을 충족하기 위해서는 

1. arr[n-3]  ,  arr[n-1]  ,  arr[n] 을 차례로 밟는 경우

2. arr[n-2]    arr[n] 을 차례로 밟는 경우

위의 두가지 경우가 가장 최소한의 경우라고 할 수 있다. 위의 경우는 세가지 조건에 모두 위배되지 않고

두 식으로 충분히 모든 경우의 수를 계산할 수 있다는 것을 노트에 조금만 적어서 생각해보면 알 수 있다. 

그래서 down-top방식으로 dp배열에 누적합을 구해 비교 저장하는 식

1. arr[n-3]  ,  arr[n-1]  ,  arr[n] 을 차례로 밟는 경우를 누적하는 식으로 응용

dp[i] = dp[i - 3] + arr[i] + arr[i - 1];

2. arr[n-2]    arr[n] 을 차례로 밟는 경우

비교해서 저장한다.

-->>

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

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

풀이

arr[1][1]    arr[1][2]    arr[1][3]

arr[2][1]    arr[2][1]    arr[2][3]

arr[3][1]    arr[3][2]    arr[3][3]    <<----    와 같은 구조를 가지므로 무조건 같은 단(행)에 있는 숫자중에 최소값만 골라서 내려간다고 결과값이 최소가 나오지 않는다는 것을 쉽게 알 수 있었다. 그래서 각 경우의 값들을 모두 비교해줘야한다. 그러기 때문에 1번째 단부터 2,3,... N번째 단까지 한 단씩 3개의 행렬 모두에 최소의 값을 누적하여 저장하면서 내려가는 알고리즘을 짜면된다. 한 단에 3개의 배열이 존재하는데 이웃끼리는 같은 색깔로 색을 칠할 수 없다. 

이 조건을 유의하면 3가지 경우로 나눌 수 있는데

1. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서  arr[i][j]에 윗 단의 최소값을 누적하는경우

if(j == 1) arr[i][j] += Min(arr[i-1][j+1], arr[i-1][j+2]);

2. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서 arr[i][j+1]에 윗 단의 최소값을 누적하는 경우

else if(j == 2) arr[i][j] += Min(arr[i-1][j-1], arr[i-1][j+1]);

3. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서 arr[i][j+2]에 윗 단의 최소값을 누적하는 경우

else arr[i][j] += Min(arr[i-1][j-2], arr[i-1][j-1]);

위의 세가지 경우로 나누어서 코드를 짜면 된다. 

그리고 가장 마지막 단에서 누적된 3개의 배열의 값을 비교해주고 가장 최소값을 출력해 주기만 하면 된다.