JUNGOL 백열등 2

https://jungol.co.kr/problem/6326

문제

 

N개의 전등이 가로 일렬로 늘어서 있으며 왼쪽부터 순서대로 1 에서 N 까지의 번호가 매겨져 있다.

각 조명의 색상은 빨간색, 녹색 또는 파란색 중 하나다.

전등들의 색은 문자열 S로 표시되고, i ( 1≤i≤N ) 번째 전등의 색은 S의 i번째 문자가 R이면 빨강, G이면 녹색, B이면 청색이며, 처음에는 모든 전등이 켜져있다.

켜져있는 전등이 한 개 이상 있으면, 아래 세 종류의 조작을 좋아하는 순서로 좋아하는 횟수 실시할 수 있다 (조작을 한 번도 하지 않아도 상관 없다).

• A 원을 지불하고 켜진 전등 중에서 가장 왼쪽에 있는 것을 끈다.
• B 원을 지불하고 켜진 전등 중에서 가장 오른쪽에 있는 것을 끈다.
• C 원을 지불하고 켜진 전등을 한 개 선택해, 좋아하는 색으로 다시 켠다.

멀리서 이 빛의 줄을 볼 때 깨끗한 흰색으로 보이게 하고 싶다.

다만, 하나도 켜진 전등이 존재하지 않는 경우 RGB의 반복이라고 생각한다.

초기 전등의 상태와 조작에 필요한 금액의 정보가 주어졌을 때,
전등의 색 배열을 RGB반복으로 하는데 필요한 금액의 최솟값을 구하는 프로그램을 작성하시오.

 

N은 20만 이하의 정수이다.

 

접근&풀이

 

 

현재 위치에서 원래 문자열이 어떤 문자인지 상태로 정의하고 dp 점화식을 세우면 되겠다고 생각했다. 

예를 들어 지금 상태를 'R'로 정했다면 이전이 빈칸이거나 'B'여야 할 것이다. 

그리고 초기에는 모두 불이 켜져 있으며, 양쪽에서 하나씩 끌 수 있기 때문에, 왼쪽에서 끈 불과 오른쪽에서 끈 불 또한 

상태로 정의했다.

 

		if(s[i-1] == 'R') {
			dp[i][0] = min(dp[i-1][2], dp[i-1][3]);
			dp[i][1] = dp[i-1][0]+c;
			dp[i][2] = dp[i-1][1]+c;
			dp[i][3] = dp[i-1][3]+a;
			dp[i][4] = min({dp[i-1][4], dp[i-1][2], dp[i-1][3]})+b;
		}

 

지금 상태와 문자열이 상이하다면 비용이 발생할 것이고, 같다면 그대로 넘기면 전이가 매우 수월하게 된다.

최솟값 dp이므로 초깃값을 inf로 설정해두는 것 또한 잊지 말자.

 

 

정답코드

 

#include <bits/stdc++.h>
#define inf 1000000000000000
#define int long long
using namespace std;
int dp[202020][5];
/* 
0 = R
1 = G
2 = B
3 = l-
4 = r-
*/
int32_t main() {
	int n, a, b, c;
	string s;
	cin >> n;
	cin >> s >> a >> b >> c;
	
	for(int i = 0; i <= n; i++) 
		for(int j = 0; j < 5; j++)
			dp[i][j] = inf;
			
	dp[0][3] = dp[0][4] = 0;
	
	for(int i = 1; i <= n; i++) {
		if(s[i-1] == 'R') {
			dp[i][0] = min(dp[i-1][2], dp[i-1][3]);
			dp[i][1] = dp[i-1][0]+c;
			dp[i][2] = dp[i-1][1]+c;
			dp[i][3] = dp[i-1][3]+a;
			dp[i][4] = min({dp[i-1][4], dp[i-1][2], dp[i-1][3]})+b;
		}
		if(s[i-1] == 'G') {
			dp[i][0] = min(dp[i-1][2], dp[i-1][3])+c;
			dp[i][1] = dp[i-1][0];
			dp[i][2] = dp[i-1][1]+c;
			dp[i][3] = dp[i-1][3]+a;
			dp[i][4] = min({dp[i-1][4], dp[i-1][2], dp[i-1][3]})+b;
		}
		if(s[i-1] == 'B') {
			dp[i][0] = min(dp[i-1][2], dp[i-1][3])+c;
			dp[i][1] = dp[i-1][0]+c;
			dp[i][2] = dp[i-1][1];
			dp[i][3] = dp[i-1][3]+a;
			dp[i][4] = min({dp[i-1][4], dp[i-1][2], dp[i-1][3]})+b;
		}
	}
	cout << min({dp[n][3], dp[n][4], dp[n][2]});
}