BOJ 1149 - RGB거리

문제 링크

---

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

문제 해결

---

1. dp[i][1~3] = i번째 집에 Red or Green or Blue를 칠할 때 드는 비용.

2. 이웃한 집에는 같은 색을 칠할 수 없고, N번째 집까지 칠했을 때 최소 비용을 구한다.  

주의할 점

---

1. dp라는 배열을 이용해서 바로바로 저장하면서 값을 구할 수 있다.

2. 이웃한 집의 색은 이전 집만 겹치지 않게 구현한다면 결과적으로 양 옆으로 겹치지 않게 된다.

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<cstdio>
	#include<cstdlib>
	#include<iostream>
	#include<vector>
	#include<algorithm>
	#include<string.h>
	#include<string>
	#include<functional>
	#include<queue>
	#include<stack>
	#include<cstring>
	#include<cmath>
	#include<climits>
	#include<map>
	#include<set>
	using namespace std;
	int N;
	int dp[1005][5];
	int main(){
	cin >> N;
	for(int i=1;i<=N;i++){
	scanf("%d %d %d",&dp[i][1],&dp[i][2],&dp[i][3]);
	// caution 1 && 2
	dp[i][1] += min(dp[i-1][2],dp[i-1][3]);
	dp[i][2] += min(dp[i-1][1],dp[i-1][3]);
	dp[i][3] += min(dp[i-1][1],dp[i-1][2]);
	}
	printf("%d",min(dp[N][1],min(dp[N][2],dp[N][3])));
	return 0;
	}

view raw BOJ 1149.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.