https://www.acmicpc.net/problem/17404
이 문제는 RGB거리 문제의 발전형이다 기존에는 사이클을 검사안했으나 이번에는 사이클을 검사해야한다 그래서 이문제를 풀기위한 핵심은
첫번째 집의 색깔을 정해주고 나머지 집들의 dp를 돌리는 것이다
어떻게 정하면 되는지는 우리는 원래 dp 를 풀때 각라인의 최솟값을 넣는데 이 최솟값을 만들 때 우리는 나머지 선택을 하지못하게 하면된다
해당 예제를 예시로 보자
평소에 우리가 dp를 구할 때 우리는 26 40 83을 min 때리고 이를 바탕으로 다음라인에서 비교 해준다 평소대로 하게된다면 우리는 다음 dp 행을 구할 때 최소 색깔을 선택함으로 우리가 색을 정할 수가 없다 만약에 우리가 999999 40 999999 이런식으로 dp 행을 놓게 된다면 무조건적으로 40이 선택된다 이러한 로직을 바탕으로
for (int first = 0; first < 3; first++) {
for (int i = 0; i < 3; i++) {
if (first == i) {
dp[0][i] = arr[0][i];
}
else {
dp[0][i] = maxVal;
}
}해당 로직이 작성된다 first는 첫번째 집이 고른 색이다 첫번째 집이 빨간색을 골랐을 때 우리는 파란색 초록색을 고르는 선택지를 없애버리기 위해서 dp행이 첫번째의 고를 선택지 에서 지워버리는 것이다
이로직 뺴고는 dp 점화식 자체는 별반 다른지 않다
내가 빨간색을 선택했을 때 이전에 초록색 혹은 파란색을 선택했을 때 의 값중 최솟 값을 선택하면된다
즉 점화식 자체는
for (int i = 1; i < n; i++) {
dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
}이렇게 된다
전체 코드는 아래와 같다
#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001][3];
int dp[1001][3];
int maxVal = 987654321;
int answer = 987654321;
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
cin >> arr[i][j];
}
}
for (int first = 0; first < 3; first++) {
for (int i = 0; i < 3; i++) {
if (first == i) {
dp[0][i] = arr[0][i];
}
else {
dp[0][i] = maxVal;
}
}
for (int i = 1; i < n; i++) {
dp[i][0] = arr[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = arr[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = arr[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
}
for (int i = 0; i < 3; i++) {
if (first == i)
continue;
answer = min(answer, dp[n-1][i]);
}
}
cout << answer;
}'백준(코테준비) > DP' 카테고리의 다른 글
| 백준 17396 / CPP (0) | 2024.11.28 |
|---|---|
| 프로그래머스 LV3 / 정수 삼각형 /DP/ C++ (1) | 2024.11.21 |
| 백준 17396 /CPP 다익스트라 (0) | 2024.10.17 |
| 백준 1956/C++ (0) | 2024.10.17 |
| 백준 2133 / c++ (0) | 2024.08.15 |