[DP] 백준 문제 풀이 - 17404 RGB거리 2

👩🏻‍💻 문제링크

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

17404번: RGB거리 2

 

✍️ 아이디어

1. 문제 이해

• RGB 거리 1과 비슷해 보이지만 마지막 집이 첫번째 집과 이웃한다는 점이 다르다
• 가장 싸게 모든 집을 페인트칠 하는 알고리즘 근데 인접한 집은 다른 색으로 페인트칠 해야함
• 앞집이 빨초파 인 경우로 나눠야함 앞집이 빨간색이면 다음집은 초록과 파란집중에 작은것을 골라야함

2. 난 처음에 백트래킹 처럼 어떤 집을 선택하였는지 싹다 기록하려고 하였으나 쉽지않음 

3. 그저 맨 앞집이 빨간집,초록집,파란집인 경우를 각각 반복문으로 굴려주면 된다(맨 앞집을 고정!!!)

ex)맨 앞집이 빨간집이면 마지막 집에서 초록 파란집중에 골라야함

 

4. 강의 안들었으면 못풀었을듯, 처음 집을 고를때  min에 선택되지 않도록 매우 큰 수를 넣는 구현 방법을 생각 못했을것 같다

 

5. 내가 생각한것중에 하나가 2~n-1번째 까지 구하고 마지막 1,n번째를 더해서 최솟값을 구하는거였는데 이건 반례가 있을듯

(경우의 수)

1. 1번집이 R이고 마지막집이 R일때 최소비용(x)

2. 1번집이 R이고 마지막집이 G일때 최소비용

3. 1번집이 R이고 마지막집이 B일때 최소비용

4. 1번집이 G이고 마지막집이 R일때 최소비용

5. 1번집이 G이고 마지막집이 G일때 최소비용(x)

6. 1번집이 G이고 마지막집이 B일때 최소비용

7. 1번집이 B이고 마지막집이 R일때 최소비용

8. 1번집이 B이고 마지막집이 G일때 최소비용

9. 1번집이 B이고 마지막집이 B일때 최소비용(x)

✍️소스코드

• 내 코드 + 강의 참조

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

long long result[1001][3];
long long color[1001][3];

int main()
{
	int n; cin>>n;
	long long ans = 10000001;
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=2; j++)
		{
			cin>>color[i][j];
		}	
	}
	
	for(int first=0; first<=2; first++) //첫집이 빨간경우, 초록경우, 파란경우를 나눔
	{
		for(int i=0; i<=2; i++)//첫집 색칠하기
		{
			if(first==i)
				result[1][i]=color[1][i];
			else{
				result[1][i]=10000001; // 조건이 아닌경우 min에서 선택되지않기 위해 큰수를 넣음
			}
		}
		
		for(int i=2; i<=n; i++)
		{
			result[i][0]=color[i][0]+min(result[i-1][1],result[i-1][2]);
			result[i][1]=color[i][1]+min(result[i-1][0],result[i-1][2]);
			result[i][2]=color[i][2]+min(result[i-1][1],result[i-1][0]);
		}
		
		for(int i=0; i<=2; i++) //마지막 집 색칠하기
		{
			if(first==i) continue;
			ans=min(ans, result[n][i]);
		}	
	}
	
	cout<<ans<<'\n';
}

 

 

체감난이도	걸린시간	참고	사용 문법
상	1hour	강의 참고	이차원 DP