문제

백준 1149번 문제

DP를 사용하는 문제

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[1004][3];
int dp[1004][3];

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> arr[i][j];
        }
    }

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

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

    
    cout << min(min(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]);

    return 0;
}

풀이

최근에 DP를 많이 풀어서인지 빠른 시간 내에 풀 수 있었다

위 문제와 같이 이전 단계에 제약 조건이 걸릴 경우 DP를 2차원 배열로 해서 푸는 경우가 많다

어떤 문제냐면 N번째 집까지 있는 데 각 집을 빨강, 초록, 파랑 중 하나의 색으로 칠해야 하고 각 색깔 별로 칠하는 데 비용이 주어진다

그래서 N번째 집까지 조건을 만족하며 하나의 색을 골라 칠하면서 비용이 가장 적게 드는 방법을 찾아라

문제의 조건은 요약하자면 다음과 같다

집 앞 뒤로 똑같은 색을 칠하지 못하게 하라. 즉, 이전 집과 똑같은 색을 칠하지 못하게 막으면 알아서 다음 집과는 똑같은 색을 못 칠한다

그래서 나는 DP 배열을 다음과 같이 정의했다

DP[i][j] (0 <= i < N, 0 <= j < 3)
i번째 집을 j번째 색으로 칠할 때 이때까지의 최소 비용

처음 dp[0][0] ~ dp[0][2]는 기본 arr[0][0] ~ arr[0][2]로 초기화

그리고 1번째 집부터 N - 1 번째 까지 루프를 돌린다

dp[i][0]은 i번째 집을 0(빨강)으로 칠하는 경우이므로 이전 집을 1(초록), 2(파랑)으로 칠한 경우 중 최소 비용과 arr[i][0]을 더해준다

나머지도 똑같이 해준다

그렇게 N-1번째 집까지 dp 배열을 완성하고 dp[N-1][0] ~ dp[N-1][2]까지의 값 중 최솟값을 출력하면 끝