DP문제들

1. 1로 만들기

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

구현

• 4부터 n까지 순회한다. 그 이유는 1은 목표점이라서 0,
  2,3은 -1 /2 /3으로 한번에 1로 갈 수 있으므로 1 고정이기 때문.
• 기본적으로 dp[i] = dp[i-1] + 1 으로 정의해둔다.
• 2로 나눌 수 있고, dp값보다 더 작다면 수정한다.
• 3으로 나눌 수 있고, dp값보다 더 작다면 수정한다.
  기본적으로 3으로 나누는 것이 횟수를 단축할 수 있어서
  제일 마지막 if문으로 둔다.

문제점
1. 갑자기 dp를 사용해서 풀려고 하니까 구현이 막막했다.
아래의 풀이를 익혀둔다.

#include <iostream>
using namespace std;

int dp[1000001]={0, };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    dp[0] = dp[1] = 0;
    dp[2] = dp[3] = 1;

    for(int i=4; i<=N; i++)
    {
        dp[i] = dp[i-1] + 1;
        if(i%2==0)
        {
            dp[i] = min(dp[i/2]+1, dp[i]);
        }
        if(i%3==0)
        {
            dp[i] = min(dp[i/3]+1, dp[i]);
        }
    }  

    cout << dp[N];

    return 0;   
}

2. 2xn - 2x1로 타일링

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

구현

• 2xn에서 2x1을 채우는 방법은 1가지,
  2x2를 채우는 방법은 2가지이다.
• 2x3을 채우는 방법은, 앞의 1칸을 2x1로 채웠다고 가정하고,
  남은 2칸을 채우면 된다, 이건 2x2를 채우는 방법과 같다.
• 추가로, 앞의 2칸을 어떻게든 채웠다고 가정하고,
  남은 1칸을 채우면 된다, 이건 2x1을 채우는 방법과 같다.
  (왜 2칸을 채우는데 x2를 하지 않는가 하면,
  세로로 채우는 경우는 1칸을 채우는 경우와 중복된다)
• dp[i] = dp[i-1] + dp[i-2]

문제점
1. 헷갈린다.

#include <iostream>
using namespace std;

int dp[1001] = {0, };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N;
    cin >> N;

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3;i<=N;i++)
    {
        dp[i] = (dp[i-1] + dp[i-2]) % 10007;
    }

    cout << dp[N];

    return 0;   
}

3. 2×n 타일링 - 2x2 추가

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

구현

• 2번 문제대로 풀면 된다.
• 2x2타일이 추가되었으니,
  식을 다음과 같이 바꾸면 된다.
  dp[i] = (dp[i-1] + dp[i-2]*2)

문제점
1. 기존 문제를 이해했다면 쉽게 풀 수 있던 문제

4. 1,2,3 더하기

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

구현

• 특정 수를 1,2,3의 합으로 표현하는 가짓수를 구하는 문제
• dp 1 2 3을 구해두고, 아래의 식을 사용하면 된다.
  dp[1] = 1; dp[2] = 2; dp[3] = 4;
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
• 의미는,
  1을 더해놨을 때, 나머지 알아서 채워라.
  2를 더해놨을 때, 나머지 알아서 채워라.
  3을 더해놨을 때, 나머지 알아서 채워라.
  이런 말이다.
  타일링 문제와 비슷한 개념.

5. 1,2,3 더하기 +

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

구현

• 123더하기와 거의 다른 문제라고 생각한다.
• 이전 123더하기가 1더해놓고 나머지 알아서해였다면,
  이번에는 1이 마지막이니까 알아서 해 라고 볼 수 있겠다.
• 다음의 식을 사용한다.
  dp의 의미는, 현재 i 숫자를 구현하기 위한 마지막 숫자를
  1 or 2 or 3으로 정해놓았다는 이야기이다.

        dp[i][1] = ((dp[i - 1][2] + dp[i - 1][3])) % 1000000009;
        dp[i][2] = ((dp[i - 2][1] + dp[i - 2][3])) % 1000000009;
        dp[i][3] = ((dp[i - 3][1] + dp[i - 3][2])) % 1000000009;

• dp[i][1]이면, 마지막이 1이니까,
  앞의 식은 2로 끝나거나 3으로 끝나야만 한다.
  그 점화식을 적은 것.
• 출력시에는 dp[N][1] + dp[N][2] + dp[N][3]를 출력한다.

문제점
1. dp 자체에는 1000000009로 나눠서 int값이 들어가지만,
마지막에 출력시에 dp값을 3개나 합하므로,
dp값이 long long범위가 될 수 있다.

따라서 출력을 long long으로 전환하고 출력해야만 했는데,
이 문제를 생각하지 못해서 고생했다.

#include <iostream>
#include <cstring>

using namespace std;

int dp[100001][4]; // 주의

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    memset(dp, 0, sizeof(dp));

    dp[1][1] = dp[2][2] = 1;
    dp[3][1] = dp[3][2] = dp[3][3] = 1;
    for (int i = 4; i <= 100000; i++)
    {
        dp[i][1] = ((dp[i - 1][2] + dp[i - 1][3])) % 1000000009;
        dp[i][2] = ((dp[i - 2][1] + dp[i - 2][3])) % 1000000009;
        dp[i][3] = ((dp[i - 3][1] + dp[i - 3][2])) % 1000000009;
    }

    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N;
        // 오류가 가장 많이 났던 부분.
        // 출력은 dp를 3개 더해야하는데 int로 하면 안되므로, 첫항을 longlong으로 바꾸어
        // longlong값이 나오게 하고, 그 값을 1000000009으로 나머지한 규칙대로 출력
        cout << ((long long)dp[N][1] + dp[N][2] + dp[N][3])%1000000009 << "\n";
    }

    return 0;
}

6. 계단 수

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

구현

• 각 자리 수가 이전 자리와 1만 차이가 나야 했다.
  그래서 2차원 배열을 만들었다. [자리수][맨마지막수]
• 위를 생각했다면 사실 끝.

문제점
1. dp를 여러개 더하고 그 값을 특정 변수에 저장한다면,
무조건 long long을 써라..
분명 다 맞는데 1%에서 자꾸 틀렸다면 의심해보기.

#include <iostream>
using namespace std;

int dp[101][10];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=1;i<=9;i++)
    {
        dp[1][i] = 1;
    }
    dp[1][0] = 0;

    int N;
    cin >> N;

    for(int i=2;i<=N;i++)
    {
        for(int j=0;j<=9;j++)
        {
            if(j==0)
            {
                dp[i][0] = (dp[i-1][1])%1000000000;
            }
            else if(j==9)
            {
                dp[i][9] = (dp[i-1][8])%1000000000;
            }
            else
            {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%1000000000;
            }
        }
    }

    long long result = 0;
    for(int i=0;i<=9;i++)
    {
        result += (dp[N][i])%1000000000;
    }

    cout << result %1000000000;

    return 0;   
}

7. 카드 깡

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

구현

• N개를 사기 위한 가장 비용이 큰 경우를 찾는 문제.
• dp를 i개를 사기 위한 최대 비용으로 두고 푼다.
• dp는 아래의 식에서 i를 1부터 N까지 돌린다.
  j는 얼마나 뺄지 정하는 값으로, 1부터 i까지 돌린다.
• dp[i] = max(dp[i], dp[i - j] + arr[j]);

문제점
1. dp문제에 더럭 겁을 먹는 것 같았다.
하지만 점화식만 찾으면 정말 쉬운 문제.

for (int i = 1; i <= N; i++)
   {
       for (int j = 1; j <= i; j++)
       {
           dp[i] = max(dp[i], dp[i - j] + arr[j]);
       }
   }

8. 카드 깡 2

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

구현

• N개를 사기 위한 가장 비용이 작은 경우를 찾는 문제.
• 위의 문제에서 수정할 부분은 3가지.
• 1 dp배열의 초기화를 99999 이런 값으로 한다.
• 2 dp[0]과 dp[1]로 초기값을 정의한다.
  (그 전에는 max해서 0으로 초기화해둔게 상관없었다)
• 3 max대신 min으로 dp 점화식을 작성한다.
  dp[i] = max(dp[i], dp[i - j] + arr[j]);

문제점
1. 없

9. 이친수

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

구현

• 0과 1만 써야하는 식에서,
  맨 앞은 0이면 안되고, 1이 연속해서 2번 나오면 안된다.
• 따라서 무조건 10~ 으로 시작하는 수일 것이고,
  3부터 dp를 작성하였다.
• dp는 현재 (몇번째) 문자인지, (마지막 문자)가 0인지 1인지
  위를 표시했다. (상당히 많이 쓰이는 전형적인 포맷?)
• 그렇게 현재 문자가 1인경우, 현재 문자가 0인 경우에 대해
  dp를 하면 끝

문제점
1. dp를 더하는 값을 저장하는건 무조건 long long

    memset(dp, 0, sizeof(dp));

    dp[1][1] = 1;
    dp[2][0] = 1;

    for(int i=3;i<=N;i++)
    {
        dp[i][1] = dp[i-1][0];
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
    }

10. 가장 긴 증가 수열

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

구현

• dp는 1로 초기화시킨다. 왜냐면 본인 자신만 있어도 길이 1.
• 2중 for문을 돌며, 본인보다 큰 값을 확인한다.
  그렇게 본인보다 큰 원소들을 증가시켜놓는다.
• 무슨 원소가 들어갔는지는 의미가 없기 때문에,
  max를 이용하여 그냥 본인의 최대값만 신경쓰면 된다.
• 그냥 생각나는대로 구현하면 된다.

문제점

• 없

    for(int i=1;i<N;i++)
    {
        for(int j=i+1;j<=N;j++)
        {
            if(arr[i] < arr[j])
            {
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }

11. 가장 긴 증가 수열 +

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

구현

• bt라는 백트래킹 인덱스를 담을 배열을 만들고,
  갱신될 때, 해당 원소의 인덱스에 이전 원소의 인덱스 값을 담도록
  구성하였다.

// 갱신이 되어야 한다면, 해당 인덱스를 j의 이전 원소라고 표시
                if(dp[i]+1 > dp[j])
                {
                    bt[j] = i;
                    lastIdx = j;
                }

• 그렇게 dp로 최대 수열 길이 구해놓고,
  bt배열로 역추적하며 stack에 쌓아서 뒤집어서 경로를 정방향 출력하고.

문제점
1. 게시판의 모든 반례가 다 정상적으로 되는데
1%도 못가고 틀렸다고 나온다.

#include <iostream>
#include <stack>

using namespace std;

int dp[1001];
int bt[1001] = {0, };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // 1로 초기화
    fill(dp, dp+1001, 1);

    int N;
    cin >> N;

    // 입력
    int arr[N+1] = {0, };
    for(int i=1;i<=N;i++)
    {
        cin >> arr[i];
    }
    
    int lastIdx=0; // lastIdx는 가장 마지막 = 가장 큰 값의 인덱스를 저장할 변수
    for(int i=1;i<N;i++)
    {
        for(int j=i+1;j<=N;j++)
        {
            if(arr[i] < arr[j])
            {
                // 갱신이 되어야 한다면, 해당 인덱스를 j의 이전 원소라고 표시
                if(dp[i]+1 > dp[j])
                {
                    bt[j] = i;
                    lastIdx = j;
                }
                // dp 갱신
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }

    // 갱신된게 하나도 없다면, 아무거나 출력하고 종료
    if(lastIdx == 0)
    {
        cout << "1\n";
        cout << arr[1];
        return 0;
    }

    // 1 dp로 가장 긴 길이 출력
    int result = 0;
    for(int i=1;i<=N;i++)
    {
        result = max(result, dp[i]); 
    }
    cout << result << "\n";

    // 2 인덱스를 역추적하여 stack에 담음(역추적한 값을 뒤집기 위함)
    stack<int> back;
    back.push(arr[lastIdx]);
    while(true)
    {
        int backIdx = bt[lastIdx];
        if(backIdx == 0)
        {
            break;
        }

        back.push(arr[backIdx]);
        lastIdx = backIdx;
    }

    // 2-2 stack을 출력하여 경로 출력
    while(!back.empty())
    {
        cout << back.top() << " ";
        back.pop();
    }
    

    return 0;   
}

왜??
일단 스킵.

다시 풀이

#include <iostream>
#include <stack>

using namespace std;

int dp[1001];
int bt[1001] = {0, };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // 1로 초기화
    fill(dp, dp+1001, 1);

    int N;
    cin >> N;

    // 입력
    int arr[N+1] = {0, };
    for(int i=1;i<=N;i++)
    {
        cin >> arr[i];
    }
    
    for(int i=1;i<N;i++)
    {
        for(int j=i+1;j<=N;j++)
        {
            if(arr[i] < arr[j])
            {
                // 갱신이 되어야 한다면, 해당 인덱스를 j의 이전 원소라고 표시
                if(dp[i]+1 > dp[j])
                {
                    bt[j] = i;
                }
                // dp 갱신
                dp[j] = max(dp[j], dp[i] + 1);
            }
        }
    }


    // 1 dp로 가장 긴 길이 출력
    int lastIdx=0; // lastIdx는 가장 마지막 = 가장 큰 값의 인덱스를 저장할 변수
    int result = 0;
    for(int i=1;i<=N;i++)
    {
        result = max(result, dp[i]); 
        if(result == dp[i])
        {
            lastIdx = i;
        }
    }
    //cout << lastIdx << "\n";
    // 갱신된게 하나도 없다면, 아무거나 출력하고 종료
    if(lastIdx == 0)
    {
        cout << "1\n";
        cout << arr[1];
        return 0;
    }

    cout << result << "\n";

    // 2 인덱스를 역추적하여 stack에 담음(역추적한 값을 뒤집기 위함)
    stack<int> back;
    back.push(arr[lastIdx]);
    while(true)
    {
        int backIdx = bt[lastIdx];
        if(backIdx == 0)
        {
            break;
        }

        back.push(arr[backIdx]);
        lastIdx = backIdx;
    }

    // 2-2 stack을 출력하여 경로 출력
    while(!back.empty())
    {
        cout << back.top() << " ";
        back.pop();
    }
    

    return 0;   
}

문제가 되었던 부분은 lastIdx였다.
무조건 맨 마지막을 가리키게 되어서
7
1 2 3 4 1 2 3 일 경우, 1 2 3을 출력하게 되었다.
따라서 갱신 위치를 수정하니 해결되었다.

12. 연속 합

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

구현

• 이전의 값을 더한 것보다 크면, dp를 갱신한다.
• dp는 현재 원소까지 가장 큰 값 (이전 dp보다 크다는 얘기는 아님)
• dp를 구하는 중에 result에 max값을 저장해둔다.
• result를 -99999로 하는 이유는, 음수도 나올 수 있기 때문.

문제접
1. 그냥 구현하라고 하면 시간이 엄청 걸릴 것 같다.
(순서를 어떻게 해야할지 포함해야할지 말아야할지 등등)
그냥 익혀두자.

#include <iostream>
using namespace std;

int dp[100001] = {0, };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int arr[N] = {0, };
    for(int i=1;i<=N;i++)
    {
        cin >> arr[i];
        dp[i] = arr[i];
    }

    int result = -999999;
    for(int i=1;i<=N;i++)
    {
        if(dp[i] < dp[i-1] + arr[i])
        {
            dp[i] = dp[i-1] + arr[i];
        }
        
        if(dp[i] > result)
        {
            result = dp[i];
        }
    }

    cout << result;
    return 0;   
}

13. 제곱수 합

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

구현

• 입력받은 수를 제곱의 합으로 표현할 때, 항이 가장 작은 수를 구하면 된다.
• 먼저 dp를 본인 자신으로 초기화한다(1의 제곱의 합)
• 2중 for문을 거치며, min값으로 dp를 수정해나간다.
• i에서 j의 제곱을 뺀 값을 for문으로 모든 j에 대해 구하며,
  가장 작은 값을 min으로 둔다.

    for(int i=1; i<=N; i++)
    {
        for(int j = 1; j*j<=i; j++)
        {
            dp[i] = min(dp[i], dp[i-j*j]+1);
        }
    }

문제점
1. 해당 점화식을 생각해내지 못해서,
i=1부터 sqrt 100000까지 dp를 1로 초기화해두고,
나머지를 구하려고 생각했었다.
2. DP의 규칙이 조금 보이는데,

• dp는 for문을 돌면서 처음부터 1~N 순서대로 초기화해야하고,
• min이나 max를 통해 본인 DP와 특정 값을 비교하는 행위를 하게 된다.

14. 합 분해

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

구현

• 0부터 N까지 K개를 더해서 표현하는 경우의 수를 구하는 문제.
• 0도 더할 수 있다는게 관점이다.
• dp[a][b]=c 라면, 정수 a개를 더해서 b를 만들 수 있는 경우는 c개라는 말
• 따라서 dp[i][j]=(dp[i-1][j]+dp[i][j-1]
• dp[i-1][j]는 0이 마지막에 더해질 경우를 의미
• dp[i][j-1]는 개수는 다 채웠지만 1이 더해질 경우를 의미
  (왜? 개수는 다 채웠는데 왜 1을 더해서 개수를 증가시킬까?)

문제점
1. 완벽히 이해 못했다.

https://sdev.tistory.com/1274
풀이를 참고하였다.

#include <iostream>
using namespace std;

long long dp[201][201] = {0, };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;

    dp[0][0]=1;
    for(int i=1;i<=K;i++)
    {
        dp[i][0]=1;
        for(int j=1;j<=N;j++) dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000;
    }

    cout << dp[K][N];
    
    return 0;   
}

복습필요
1. 14번문제 이해 안 됨.
2. DP문제들 푸는 방식 잘 보기

• 먼저 시작점을 구하고,
• 시작점 다음부터 ~N까지 for문으로 차곡차곡 값을 생성함.

3. 증가수열 풀이 익히기