💎 문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
💎 입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
💎 출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
💎 풀이 방법
다이나믹 프로그래밍을 이용한 문제로 이전 단계와 그 다음 단계와의 구분을 명확히해서 어떤식으로 dp를 구해낼 것인지 고민하는게 중요한 문제였다. 이번 문제는 빨, 초, 파에 따른 3가지 비용이 있고 따라서 이를 따라서 N번째의 dp값 또한 3가지 경우로 나누어서 생각해볼 수 있다.
먼저 dp의 초기 값은 각각의 빨, 초, 파를 칠하는 비용으로
if(i == 0){
dp[i][0] = v[i][0];
dp[i][1] = v[i][1];
dp[i][2] = v[i][2];
}와 같이 표현하였다. 다음으로 두번째부터의 dp는 이전 값에 따라서 최소가 되는 칠하는 비용이 달라질 수 있는데 그 이유는 문제의 조건에서 보듯 이전에 칠한 색을 다음번에 똑같이 칠할 수 없기 때문이다. 따라서 색을 적절하게 골라서 어떻게 최소의 비용을 만들어낼 수 있을지가 관건인 것이다. 앞서 초기 값의 dp를 이용하여 각각의 색깔마다 칠하는 비용이 존재할 것이며 이는 앞선 경우에서 반드시 다른 색깔을 칠했을 것이다. 따라서
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i][1];
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i][2];위와 같이! 표현할 수 있을 것이다. 결국 이 식을 for문을 통해 N번 반복하게 되면 N번째의 dp의 값을 구할 수 있을 것이며 이는 3가지 색들 중 마지막으로 칠한 색을 골랐을 때 최소인 비용을 결과로 출력해주면 정답이다.
💎 전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector <int>> v(1001, vector<int>(3));
int dp[1001][3];
int N;
int main(int argc, const char * argv[]) {
int temp;
cin >> N;
for(int i = 0;i < N;i++){
for(int j = 0;j < 3;j++){
cin >> temp;
v[i][j] = temp;
}
}
for(int i = 0;i < N;i++){
if(i == 0){
dp[i][0] = v[i][0];
dp[i][1] = v[i][1];
dp[i][2] = v[i][2];
}
else{
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + v[i][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + v[i][1];
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + v[i][2];
}
}
cout << min({dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]}) << "\n";
return 0;
}
💎 고민
실버 1 문제라서 살짝 겁먹었는데 다소 생각보다 쉽게 풀 수 있었다. 이게 dp는 dp의 상태를 순차적으로 달라지며 이는 이차원 배열로도 표현이 가능하다는 것을 이번 문제에서 접근해볼 수 있었다. 항상 dp는 무조건 전 후의 관계를 잘보는 것이 중요하다는 것을 다시금 깨달았다!!
코딩테스트 진짜 열심히 해보자!! 방학 때 뭔가 해낸다는 기분을 조금씩 만들어갔으면 좋겠다..
화팅!!
