백준 1149 RGB거리

 

1149번: RGB거리

 

문제!

---

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

---

요약하면 앞뒤 집과 색이 다르게 칠하는 최소비용을 구하는 문제

 

전형적인 동적계획법 문젠거 같습니다!

 

 

바로 방법이 생각 나진 않았지만 집에 색칠을 해가면서 최소한의 비용을 계속 반복해서 계산해주는 방식일것 같습니다!

 

 

시작!

---

일단 배열 하나 선언했습니다.

int house[1001][3]={0};

여기에는 n번집이 1~3 색일때의 최솟값을 계속 계산해줄 예정입니다.

 

 

그리고 입력처리를 해줍시다.

 

첫번째값은 바로 house에 넣어주고

int main() {
	int n;
	int answer;

	cin >> n;
	cin >> house[1][0] >> house[1][1] >> house[1][2];

 

 

두번째 집 부터는 들어갈수 있는 칸에(전번 하우스 1~3번)  최솟값을 생각해주며 최신화 해줍시다.

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

		house[i][0] = min(house[i-1][1]+ dp[0], house[i - 1][2] + dp[0]);
		house[i][1] = min(house[i - 1][0] + dp[1], house[i - 1][2] + dp[1]);
		house[i][2] = min(house[i - 1][0] + dp[2], house[i - 1][1] + dp[2]);
	}

 

 

그리고 마지막 집의 값들의 최소를 구하면

 

answer = min(min(house[n][0], house[n][1]), house[n][2]);

 

 

끝....

 

코드는 짧은데 이런 동적계획법 문제에 익숙해져야 풀수있는 문제였습니다!

 

 

 

ALL

#include <iostream>
#include <algorithm>
using namespace std;
int house[1001][3]={0}; // 모든 선택지에 대한 최솟값
int dp[3]; // 각각의 집 색의 비용



int main() {
	int n;
	int answer;

	cin >> n;
	cin >> house[1][0] >> house[1][1] >> house[1][2];


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

		house[i][0] = min(house[i-1][1]+ dp[0], house[i - 1][2] + dp[0]);
		house[i][1] = min(house[i - 1][0] + dp[1], house[i - 1][2] + dp[1]);
		house[i][2] = min(house[i - 1][0] + dp[2], house[i - 1][1] + dp[2]);
	}

	answer = min(min(house[n][0], house[n][1]), house[n][2]);

	cout << answer << endl;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!