1. 1,2,3 더하기 4

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

구현

• 초기값 제대로 정하고
  dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) 이거 하면 끝.

문제점

• 없

2. RGB 거리

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

구현

• 입력은 집마다 색깔 별로 칠하는 비용이 주어진다.
  모두 다르다.
• 칠하는 방법은 이전 집과 색이 달라야만 한다.
• 최소값을 구하면 된다.
• 그냥 이 내용에 맞춰서 dp를 적으면 끝.
• dp[i][0] = min(dp[i-1][1], dp[i-1][2])+ cost[i][0];
  현재 i번째 집의 색이 0인 최소비용은,
  i-1번째의 집이 1인 비용과 i-2번째의 집이 2인 비용 중 최소에
  현재 i번째 집의 0을 칠하는 색을 더하면 된다.

문제점

• 없

#include <iostream>
using namespace std;

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

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

    int N;
    cin >> N;

    int cost[1001][3];
    for (int n = 1; n <= N; n++)
    {
        for (int i = 0; i < 3; i++)
        {
            cin >> cost[n][i];
        }
    }

    for (int i = 1; i <= N; i++)
    {
        dp[i][0] = min(dp[i-1][1], dp[i-1][2])+ cost[i][0];
        dp[i][1] = min(dp[i-1][0], dp[i-1][2])+ cost[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1])+ cost[i][2];
    }
    
    cout << min(min(dp[N][0], dp[N][1]), dp[N][2]);

    return 0;
}

3. 동물원 (2N 사자배치)

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

구현

• 2xN칸에 사자가 가로나 세로에 인접하지 않게 배치하는 경우의 수를 찾는 것.
• dp[a][b] = c 라면, a행에서 b번째 칸에 두었을 때까지의 경우의 수는 c
• 여기서 b의 값을 0, 1, 2를 가질 수 있도록 했다.
  아예 배치하지 않는 경우도 존재하므로 0으로 두기로 했다.
• 그냥 다른 dp문제처럼 차근차근 for문 돌리면 해결.

문제점

1. 분명히 첫째줄에 사자를 배치하라고 했다.
그렇다면 dp[1][0]은 당연히 0으로 생각을 하고 풀었는데,
문제가 오해의 소지가 다분한건지, dp[1][0]을 1로 두고 풀어야만
정답이 된다.

#include <iostream>
#include <cstring>
using namespace std;

long long dp[100001][3];

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

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

    int N;
    cin >> N;

    // 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.
    dp[1][0] = 1;   // 배치하지 않는 경우도 경우로 친다?
    dp[1][1] = 1;
    dp[1][2] = 1;

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

    cout << (dp[N][0] + dp[N][1] + dp[N][2]) % 9901; 

    return 0;   
}

4. 오르막 수

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

구현

• 이전 수보다 이상인 수가 현재 나와야하는 수를 구해야한다.
• 입력으로는 자릿수가 주어지고, 해당 자릿수에서 나올 수 있는
  모든 오르막 수의 개수를 구하면 된다.
• 그냥 말 그대로 구현하면 끝.
• 보통 DP가 뭔가 자릿수랑 관련있으면 무조건 자릿수를 하나의 항으로 두고,
  그 자릿수의 뭔가 표시할 만한 것을 추가 항으로 두면 된다.

// i는 현재 자릿수, k는 현재 자릿수의 숫자, z는 현재 자릿수 이전의 숫자들
for (int i = 2; i <= N; i++)
    {
        for (int k = 0; k <= 9; k++)
        {
            for (int z = 0; z <= k; z++)
            {
                dp[i][k] += (dp[i - 1][z])%10007;
            }
        }
    }

• 복잡해 보여도 간단한 3중 for문

문제점
1. result에 모듈러 연산을 해야했는데,
result 더하는 식에 모듈러를 해서 틀렸었다.

for (int i = 0; i < 10; i++)
    {
        result += dp[N][i]; // %10007 이걸 왜 여기에했지?
    }
    cout << result %10007;

5. 스티커 대각 최대 점수

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

구현

• 동물원 사자 문제와 결은 비슷하다.
• 2XN 스티커에 점수를 매겼을 때, 특정 스티커의 점수를 획득하면,
  가로세로 인접한 스티커의 점수는 절대 얻지 못한다.
• 최고 점수를 구하면 되는 문제.
• dp[a][b] = c 라고 하면, a행의 b열까지의 점수의 최대값 c를 의미한다.
• 구현에 머리를 써야하는데,
  최대값을 위해 이전 행과는 대각선일 수밖에 없게 된다.
  이 때, 한 칸 넘는 대각선이 될 수도 있다.
  (한 칸 넘는 직선은 될 수 없는 이유가,
  그렇다면 그냥 대각대각 이동하면 최대값이 되기 때문.)
• 풀고서 찾아보았다.
  https://omyodevelop.tistory.com/51 << 참고

        // 초기값.
        dp[1][1] = arr[1][1];
        dp[2][1] = arr[2][1]; 

        // j열 각각 값을 구함
        for (int j = 2; j <= N; j++)
        {
            // 바로 전의 대각선이나, 전전의 대각선 값.
            dp[1][j] = max(dp[2][j-1], dp[2][j-2]) + arr[1][j];
            dp[2][j] = max(dp[1][j-1], dp[1][j-2]) + arr[2][j];
        }

문제점

• 문제가 뭔말인지 이해하는게 어려웠다.

6. 포도주 시식 (3연속x)

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

구현

• 포도주의 순서와 양이 각각 정해져 있다.
• 3잔 연속 마실 수 없고, 합이 가장 큰 값을 구한다.
• dp[a][b]=c 라면, a번째를 마시는 경우가 b잔연속째라면,
  시식할 수 있는 최대 양은 c이다.

// 입력과 동시에 초기값 설정
    for(int i=1;i<=N;i++)
    {
        cin >> arr[i];

        dp[i][0] = 0;
        dp[i][1] = arr[i];
    }
    dp[1][2] = 0;
	
    // DP
    for(int i=2;i<=N;i++)
    {
        // 1 현재 와인을 안마셨을때 최대값
        dp[i][0] = max(max(dp[i-1][1], dp[i-1][2]), dp[i-1][0]); 

        // 2 현재 와인을 마셨을때 최대값
        dp[i][1] = dp[i-1][0] + arr[i];
        dp[i][2] = dp[i-1][1] + arr[i];
    }

문제점
1. dp[i][0] = max(dp[i-1][1], dp[i-1][2])
라고 생각했었다.
하지만 틀린 이유는, 바로 이전에 마셨을 것을 가정했기 때문이다.
마시지 않았을 수도 있다. (3번째라서)
따라서 아래처럼 수정했다.

dp[i][0] = max(max(dp[i-1][1], dp[i-1][2]), dp[i-1][0]); 

7. 정수 삼각형

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

구현

• DP의 정석이라고 할 수 있는 문제라고 안다.
• 트리를 내려가며 최대 합을 구하는 문제이다.
• 트리의 구조처럼 대각선으로 내려갈 수 밖에 없도록 구현하는게 관건.
• 구현은 쉽다.

    dp[1][1] = tree[1][1];

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

문제점
1. int result라고만 쓰고,
result = 0 으로 초기화를 하지 않아서 자꾸 쓰레기값이 나왔다.