백준 1149번 : RGB거리

ntbij29·2021년 3월 5일
0

알고리즘 공부

목록 보기
41/41
post-thumbnail

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

여유있을 때, 어려운 문제 풀어보도록 하자.

문제 읽기

연속되게 색깔이 칠해져서는 안된다. 이번 문제는 RGB 총 3가지의 경우가 있으므로 int ans = min(c1, min(c2,c3)) 이런 식으로 진행해야 할 것 같다. 어떻게 해야 하는지 생각해보자.

N이 1000개 이므로 오류가 나면 long long 까지 고려해야겠다. 우선은 배열로 접근하자.

i번째 집을 확인(R로 칠했다고 가정)하기 위해서는 i-1번째 집의 색깔을 확인(G 또는 B)해야 한다. i-2번째 집은 i-1번째 집을 계산할 때 이미 계산되기 때문에 그 전까지는 고려하지 않아도 된다.

RGB를 선택했다는 것은 0, 1, 2로 표현하거나 arrR[i]를 0으로 바꿔줘야 할 것 같다. 아니면 바꾸면서 bool bR = true;로 표현하여 if문을 구성할 때 if(bR) {G와 B만 고려함} 이런식으로 하는 것도 괜찮을 것 같다. 그럼 min을 못쓰겠구나.

코드

#include<iostream>
#include<algorithm>
using namespace std;

int rgb[1001][3]{ 0, };
int cost[3]{ 0, };

int main() {
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> cost[0] >> cost[1] >> cost[2];
		rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) + cost[0];
		rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + cost[1];
		rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + cost[2];
	}
    
	cout << min(rgb[N][0], min(rgb[N][1], rgb[N][2]));
	return 0;
}

분석

오. 할말이 많다. 처음에 고려했을 때에는 if문을 사용해서 전에 무엇을 사용했는지 확인을 했었다. 예제 답은 나오는데 오답으로 뜨길래 #define ll long long int를 선언하여 저번처럼 긴 정수로 인한 오답인 경우를 해결하려고 했는데 이 또한 오답이 떴다.

그래서 검색을 하고.. 보니 애초에 배열을 1001*3 배열로 받아서 굳이 if문으로 전의 색을 확인하지 않고도 해결할 수 있었다.

rgb[i][0] = min(rgb[i - 1][1], rgb[i - 1][2]) + cost[0];
rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + cost[1];
rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + cost[2];

이렇게 rgb[i][0]에는 현재 i에 R이 들어간다고 가정한 후, 전 집 i-1의 색깔 중에 가격이 적은 것을 선택하고 i에 들어가는 가격을 더해준 것이었다.

생각외로 dp문제는 이렇게 배열을 통해 해결한다.

profile
🛰️ 21-1

관심 있을 만한 포스트

0개의 댓글