[백준] DP

<< 이론 >>

1. DP의 정의 & 속성

     동적 계획법: 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

     두 가지 속성을 만족해야 DP로 풀 수 있다

         -optimal substructure: 문제의 정답을 다른 문제의 정답에서 구할 수 있음  ex) 피보나치 

         -overlapping subproblem: 겹치는 부분 문제 ( 작은 문제로 N-1과 N-2번째 수를 구하는 것)

         ex)서울->부산 가는 가장 빠른 길: 서울->대전-> 대구->부산 이면, 대전->부산을 가는 가장 빠른 길은 대전->대구->부산이다.

 

2. 문제 스킬

   1) 각 문제는 한 번만 풀어야 한다.

   2) 같은 문제는 구할 때마다 정답이 같다. 정답을 어딘가에 메모해두자(memorization)

   3) 문제에서 구하려고 하는 답을 문장으로 나타낸다.

   4) 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다.

 

3. 푸는 방식

1. top-down(재귀) :문제를 작은 문제로 나눈 후, 작은 문제부터 식으로 구하자. 시간 복잡도는 채워야 하는 칸의 수 * 한 칸을 채우는 복잡도(식의 복잡도)

2. bottom-up(for문): 크기가 작은 문제부터 하나도 빠짐없이 풀면서 점점 큰 크기를 풀면 언젠가는 언젠가 풀어야 하는 방식으로 풀 수 있다.

 

<< 문제 >>

1. 1로 만들기

 

1. 문제

- 3으로 나누거나(3의 배수일 떄), 2로 나누거나(2의 배수일 때), 1을 빼서 총 정수 1을 만들 때 연산의 최솟값을 구하라

 

2. DP배열 정의

 - DP[N] = N->1로 만드는데 필요한 연산의 최솟값

 

3. 풀이 과정

1) 3으로 나눌 때, D[N] = D[N/3] +1

2) 2로 나눌 때, D[N] = D[N/2] + 1

3) 1을 뺄 때, D[N] = D[N-1] + 1

D[N]을 만드는 방법은 이렇게 총 3가지인데 위의 3가지 중 최솟값이 답

 

2. 2N 타일링

 

1. 문제

-2*N직사각형을 1*2, 2*1로 채우는 방법의 수

 

2. DP배열 정의

-dp[N] = 2* N직사각형을 채우는 방법의 수

 

3. 풀이 과정

   1) dp[N] = dp[N-1](가로 길이가 1인 직사각형을 N-1 다음으로 1개 세로로 채움

   2) dp[N] = dp[N-2](가로 길이가 2인 직사각형을 N-2 다음으로 2개 가로로 채움

  => dp[N]을 만드는 방법은 이렇게 총 2가지이고, 경우의 수이므로 더한다.

-팁: 10007로 나누라는데, 버퍼 오버플로우가 생길 수 있으니 더할때마다 10007로 나누자.

 

3. 2N 타일링2

 

1. 문제

 - 2*N직사각형을 1*2, 2*1,2*2로 채우는 방법의 수

 

2. DP배열 정의

 - dp[N] = 2* N직사각형을 채우는 방법의 개수

 

3. 풀이 과정

1) dp[N] = dp[N-1](가로 길이가 1인 직사각형을 N-1 다음으로 1개 세로로 채움

2) dp[N] = dp[N-2](가로 길이가 2인 직사각형을 N-2 다음으로 2개 가로로 채움

3) dp[N] = dp[N-2](2*2인 사각형을 N-2다음으로 1개 세로로 채움)

 => dp[N]을 만드는 방법은 이렇게 총 3가지이고, 여기선 경우의 수이므로 더한다.

 

4. 카드 구매하기

 

1. 문제

- 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하라.

 

2. DP배열 정의

- dp[N] = N개를 구하기 위해 지불할 금액의 최댓값.

- p[i] =  i개의 카드가 들어간 카드팩 가격 (i는 한 팩에 들어간 카드 개수)

 

3. 풀이 과정 ( 문제에선 사야 할 금액이라고 했지만, 이해를 돕기 위해 "팔 수 있는 최댓값으로 생각")

  1) 카드 i개를 p[i]에 판다면 ->번 금액은 dp[n-i] + p[i]

  2) dp[i] =  max(dp[i], dp[i-j] + p[j]) <-이걸 2중 for문 돌림.(i,j)

 

4. 접근 방식: 마지막 사람에게 몇 개를 팔건지라는 생각으로 접근할 것!

 

5. 가장 긴 증가하는 부분 수열

 

1. 문제 &  DP배열 정의

- D[i] = A[1],A[2],...A[i]까지 수열 중 A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열 길이.

 

2. 풀이 과정 

* 원리) 

       - dp[i] = i를 마지막으로 하는 부분 수열들 중, 가장 긴 부분 수열의 길이

                =  dp[1]~dp[i-1] 값 중 가장 큰 dp값 + 1 (i를 추가하니까 길이가 1 추가됨)

       - 만약 가장 큰 dp값이 dp[j]라 하면, dp[j]는 이미 앞에서 구해진 것에 의해 증가수열일 것이다. A[j]값           이 dp[j]를 만드는 부분 수열 중에서 가장 마지막 원소일 것인데, A[i] > A[j]면 dp[i] = dp[j]+1을 수행할 수 있다.

 

* 풀이 과정(bottom up)

    - dp[i]는 반드시 A[i]가 포함되어야 한다.

    => dp[i] = max(dp[j]) +1. 이 때, 문제의 조건도 확인한다 (j<i, A[j] < A[i]) 

 

6.  가장 큰 증가하는 부분 수열

 

1. 문제 & DP배열 정의

-dp[i] = A[1],A[2],...A[i]까지 수열 중, 증가하는 부분 수열 중에서 합이 가장 큰 수열 구하기

 

 2. 풀이 과정 (bottom-up)

- dp[i]는 합을 저장해야 한다.

- dp[i] = max(dp[j]) +A[i] 이 때, 문제의 조건 확인( j<i, A[j]<A[i]). 

- dp[i] 초기값은 A[i]로 지정한다.

- 핵심 코드:

 //dp[N]을 구하기
for (int i = 0; i < N; i++) {  
	int tmp;
    for (int j = 0; j < i; j++) { 
		if (A[j] < A[i]) tmp = max(tmp, dp[j]); //j=0~i-1사이 범위 중 가장 큰 dp값을 찾는다.
    }
    dp[i] = tmp + 1;
}
 

7. 가장 긴 바이토닉 부분 수열

 

1. 문제 & DP배열 정의 

  -D[i] = A[1],A[2],...A[i]까지 수열 중,  A[i]를 기준으로 0~i-1까지는 증가, i+1~j까지는 감소하는 수열 중 가장 긴 수열의 길이를 구하라

 

2. 풀이 과정

- 가장 긴 증가 수열(D1)와 가장 긴 감소 수열(D2)를 각각 구한 후, D1[i] + D2[i]-1이 가장 큰 값

- 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

8. 연속 합

 

1. 문제

-n개의 정수로 이루어진 수열이 있을 때, 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합은?

-고려사항: 음수도 선택하는 경우가 최대 값이 될 수 있다 ex. 5, -1, 5 : 9가 최대

 

2. DP배열 정의

-D[i] = A[i]를 마지막으로 하는 최대 연속합 ("i를 포함해야 한다")

 

3. 풀이 과정 

   1)A[i-1]로 끝나는 연속합이 포함되는 경우: D[i-1] + A[i]

   2)새로운 연속합을 시작하는 경우:  A[i]

 

    => dp[i] = max(dp[i-1] + num[i], num[i]); 

  - 위 방식으로 dp배열을 N까지 채운 후, dp[1]~dp[N]값 중 최댓값을 리턴한다.

 

4.  핵심 코드

dp[0] =-1001;
for (int i=1;i<=N;i++) 
	dp[i] = max(dp[i-1] + num[i],dp[i]);
	
int result = -1001;
for (int i=1;i<=N;i++)
	result = max(result,dp[i]);
cout <<result;	

9. 계단 오르기

 

1. 문제

계단을 오르면서 얻을 수 있는 점수의 최대값을 구하라

   1) 한 계단을 밟으면서 이어서 다음 계단이나 다음 다음 계단을 오를 수 있다.

   2)연속된 세 개의 계단을 모두 밟아선 안된다(시작점 제외)

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

 

2. DP배열 정의

-dp[i]: i번째 계단을 밟았을 때 최대 점수.

-a[i]: i번째 계단을 밟았을 때의 점수

 

3. 풀이 과정 

1) 1개 연속 -> i-1번째를 밟지 않고 i를 밟은 경우, 즉 i-2를 밟고 그 다음 i를 밟은 경우

2) 2개 연속 ->  i-1번째를 밟고 i를 밟은 경우, 즉 i-3을 밟고 i-1,i를 밟은 경우

=> d[i] = max(d[i-2]+a[i], d[i-3]+a[i-1]+a[i]);

 

10. 제곱수의 합

 

1. 문제

-N은 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 그 항의 최소 개수를 구하라

     ex) 11 = 9 + 1 + 1, 4 + 4+ 1 + 1+ 1-> 답은 3

 

2. DP배열 정의

-dp[i] = i를 나타낼 수 있는 제곱수 들의 합 경우의 수 중 최소 항 개수

 

3. 풀이 과정 

-0 + 0 +...+ i^2 = N이라 할 때 dp[N] = min(dp[N-i^2]+1), (단 i^2<=N)

-시간복잡도: N*루트N

 

11. 타일 채우기

1. 문제 & DP배열 정의

- 3*N을 1*2, 2*1로 채우는 방법의 수를 구하라

-D[i] = 3*i를 채우는 방법의 수

 

2. 풀이 과정 

N=6일때 추가로 발생하는 경우의 수

-이 문제의 핵심은 3의 배수라는 것임 (n은 짝수여야 한다. 2*1, 1*2 블럭으로만 3*n을 구성해야 하기 때문에)

-위의 그림과 같은 경우의 수도 고려해야 한다는 걸 명심하기! 즉, i가 짝수라면, 해당 케이스에서만 만들 수 있는 2가지 경우의 수가 더 있다.

=> dp[i] = dp[i-2]*3 (길이가 2가 늘어날 수록 3가지 방법으로 옆에 붙일 수 있다.(dp[2] = 3이라서) 이 때 주의할 점은 +3이 아니라 *3이다.)

     dp[i] += dp[i-j]*2 (i가 짝수일 때 i에서만 만들 수 있는 두 가지 경우의 수를 더 만들 수 있다.)

 

3. 코드 

-참고: https://lmcoa15.tistory.com/42

 

12. 파도반 수열

 

1. 문제 & dp배열 정의

- dp[i] = i번째로 삼각형을 추가했을 때 가장 긴 삼각형의 변의 길이

2. 풀이과정  

-dp[i] = dp[i-1] + dp[i-5] 혹은 dp[i] = dp[i-2] + dp[i-3]

-교훈: 어렵게 나왔다고 쫄지 말자.

-틀렸던 점: dp 자료형을 long long으로 바꿔야 함

 

13. 합분해

 

1. 문제

- 0 ~ N까지의 정수 중 K개를 더해서 그 합이 N이 되는 경우의 수

- 1+2와 2+1은 서로 다른 경우이며, 한 개의 수를 여러 번 쓸 수 있음

 

2. DP배열 정의

-dp[K][N] : 정수 K개를 더해서 합이 N이 되는 경우의 수

 

3. 풀이 과정 

-포인트: 쓸 수 있는 개수가 K로 고정되어있다

- 0 + 0+ …+ L = N이라고 생각해보면  dp[k][n] = dp[k-1][N-L], (L<=N)

-유의 사항:for문의 범위를 항상 주의 하자!!!!!! for(K)안에 for(N)를 넣어야 함

 

14. 암호 코드

 

1. 문제

-알파벳을 숫자로 변환한 암호가 주어졌을 때, 그 암호의 해석으로 나올 수 있는 영어의 경우의수

 

2. DP배열 정의

- dp[i] = i번째 문자까지 해석했을 때, 나올 수 있는 해석의 가짓수

- (이전까지 구한 경우의 수 + 맨 마지막 숫자를 해석하는 가짓수)

 

3. 풀이 과정 (알파벳은 총 26개)

   1)마지막 숫자를 한자리 수 단위로 나누었으면  dp[i] += dp[i-1];( +=연산을 해야 최종 dp[n]이 n까지 해석했을 때 나올 수 있는 경우의 수가 된다.)

   2)마지막 숫자를 두자리 수 단위로 나누었으면 ( 단, 인덱스가 첫번째거나 직전 값이 0이면 두자리수 못만든다)

       dp[i] += dp[i-2];

 - 1자리 암호와 2자리 암호로 나눌 수 있어야 한다. 즉, 만들 수 있는 경우의 수는 숫자를 나눌 수 있는 방법 의 수로 구할 수 있다. 

 -팁 : s = " " + s;를 해야 index 접근이 쉽다!!!(0번째에 아무것도 없고, 첫번째에 첫번째 문자가 들어감!!!!!) 이렇게 하면 for문 범위도 1~size()로 할 수 있다.

 

4. 코드 

#include<iostream>
#include<algorithm>
#define MAX 5001
#define MOD 1000000
using namespace std;

int main() {
ios_base :: sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);

int dp[MAX] = {1}; //i번째 알파벳을 읽었을 때까지 모든 경우의 수
string s;
cin >> s;
s = " " + s;

dp[0] = 1; //첫번째는 당연히 1개  
for( int i=1; i<s.size(); i++) { //범위 조심할 것!!!  
    int ithNum = s[i] - '0'; //string 형을 int형으로 바꿈

//한자리 암호 해석
    if( 1<= ithNum && ithNum <=9) {
        dp[i] += dp[i-1]; //직전의 경우의 수
        dp[i] %= MOD;
    }

//두자리 암호 해석 
    if(i==1) continue; //두자리 수로 만들 수 없으므로 pass
    ithNum = (s[i-1]-'0')*10 + (s[i]-'0');
	if(10 <= ithNum && ithNum <=26) {
        dp[i] += dp[i-2]; //두번째 전 경우의 수 더하기
        dp[i] %= MOD;
      //    cout << "dp["<<i<<"] = "<<dp[i]<<endl;
    }
}
 cout <<dp[s.size()-1] %MOD;

}