[문제풀이] 백준 1149 - RGB 거리

📢 문제

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

📢 알고리즘

DP

📢 풀이

1. 내가 푼 풀이

#include <iostream>
#include <algorithm>

using namespace std;
int cost[1001][3]; // i번째 집을 빨, 초, 파로 칠하는 비용
int dp[1001][3];   // i번째 집을 빨, 초, 파로 칠했을 때 최소 비용(이전집 모두 칠함)

int main()
{
  int N;
  cin >> N;
  for (int i = 1; i <= N; i++)
  {
    cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
  }

  for (int i = 1; i <= N; i++)
  {
    if (i == 1)
    {
      dp[1][0] = cost[1][0];
      dp[1][1] = cost[1][1];
      dp[1][2] = cost[1][2];
    }
    else
    {
      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];
    }
  }
  int res = min(dp[N][0], dp[N][1]);
  res = min(res, dp[N][2]);

  cout << res;
}

2. 조금 더 간단한 풀이

#include <iostream>
#include <algorithm>

using namespace std;
int cost[3];     // 집을 빨, 초, 파로 칠하는 비용
int dp[1001][3]; // i번째 집을 빨, 초, 파로 칠했을 때 최소 비용(이전집 모두 칠함)

int main()
{
  int N;
  cin >> N;

  for (int i = 1; i <= N; i++)
  {
    cin >> cost[0] >> cost[1] >> cost[2];

    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[0];
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[1];
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[2];
  }
  int res = min(dp[N][0], dp[N][1]);
  res = min(res, dp[N][2]); //min 함수를 통해 값 3개를 비교하려면 2개씩 비교해야함

  cout << res;
}

• 처음에 DP 생각을 안한 건 아닌데,
  3번째 집까지의 최소비용 = 2번째 집까지의 최소비용 + 3번째 집에서의 비용
  으로만 생각해서, 3번째 집을 같이 고려하는 순간 2번째 집까지의 최소비용이 아무 의미가 없어진다고 생각했다.
  (2번째 집까지의 색칠이 3번째집 색칠에 영향을 미치므로.. 2번째 집까지 최소비용이라고 해서 3번째 집까지 고려했을 때도 최소라는 보장x)

• 하지만 2번째 집까지의 최소비용 대신
  2번째 집을 빨간색으로 칠했을 때 최소비용, 2번째 집을 초록색으로 칠했을 때 최소비용, 2번째 집을 파란색으로 칠했을 때 최소비용 으로 각각 저장하고
  3번째 집을 빨강, 초록, 파란색으로 칠하는 경우마다 저 값을 활용해서 최소비용을 구하면 해결된다!

• dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];

  • i번째 집을 빨간색으로 칠했을 때 최소비용 = min(i-1번째 집을 초록색으로 칠했을 때 최소비용, i-1번째 집을 파란색으로 칠했을 때 최소비용) + i번째 집을 빨간색으로 칠했을 때 비용

• DP를 사용하는 경우를 잊지 말자!
  : 어떤 문제의 해답에 그보다 작은 문제의 해답이 포함되어있는 경우

  🤷 정자역에서 서울시립대까지 가는 법?
  👦 정자역에서 회기역까지 가서, 10분 걸으면 돼!
  🤷 그럼 회기역까지 가는 법을 알면 되겠네. 회기역까지 어떻게 가는데?
  👦 정자역에서 왕십리역까지 가서, 경의중앙선 타면 돼!
  🤷 그럼 왕십리역까지 가는 법을 알면 되겠네. 왕십리역까지 어떻게 가는데? ...