https://www.acmicpc.net/problem/17404
17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
1149번 RGB거리(https://www.acmicpc.net/problem/1149)와 풀이는 같지만, 1번 집과 N번 집의 색이 다른 경우를 모두 해본다.
그 경우들은
빨강, 파랑
빨강, 초록
초록, 빨강
초록, 파랑
파랑, 빨강
파랑, 초록
와 같다.
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000*1000+1
int arr[1010][3];
int dp[1010][3];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
int ans = MAX;
for(int i=0; i<n; i++)
for(int j=0; j<3; j++)
cin>>arr[i][j];
for(int k=0; k<3; k++){ // 1번 집의 색을 k로 고정
for(int j=0; j<3; j++){ // dp배열 초기값
if(k == j)
dp[0][j] = arr[0][j];
else
dp[0][j] = MAX;
}
//dp 점화식 돌리기
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];
}
for(int t=0; t<3; t++){ // N번 집 색 t로 정하기
if(t == k) // 1번 집과 N번 집 색이 같으면 스킵
continue;
ans = min(ans, dp[n-1][t]);
}
}
cout << ans;
return 0;
}
'문제 풀이' 카테고리의 다른 글
[c++] 백준 2109 순회 강연 (0) | 2023.04.14 |
---|---|
[c++] 백준 2812 크게 만들기 (0) | 2023.04.14 |
[c++] 백준 13398 연속합 2 (0) | 2023.03.22 |
[c++] 백준 15988 1, 2, 3 더하기 3 (0) | 2023.03.20 |
[c++] 백준 1309 동물원 (0) | 2023.03.20 |