[Codejam][2021][QR] 2. Moons and Umbrellas

문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145

---

X = CJ 비용, Y = JC 비용. S = C, J, ? 로 이루어진 문자열

S 문자열의 ? 문자에 C 혹은 J를 대체한다고 할 때, 지불해야 하는 최소 비용을 구해라.

---

DP로 풀 수 있다.

 

dp[0][i] = S[i]가 'C' 일 때, S[~i] 까지 최소 지불금액

dp[1][i] = S[i]가 'J' 일 때, S[~i] 까지 최소 지불금액

 

dp 배열은 초기 값은 만들 수 없음을 의미하는 INF 값으로 세팅한다.

그리고 S[0]이 'C' 혹은 '?'인 경우 dp[0][0] 을 0으로 갱신한다.

또한 S[0]이 'J' 혹은 '?'인 경우 dp[1][0]을 0으로 갱신한다.

 

그리고 1 ~ N-1 까지 탐색하며 (탐색변수 = i)

S[i]가 'C' 혹은 '?' 인 경우

dp[0][i] = 최소값(dp[0][i-1](CC), dp[1][i-1](JC) + Y) 로 갱신한다.

S[i]가 'J' 혹은 '?' 인 경우

dp[1][i] = 최소값(dp[1][i-1](JJ), dp[0][i-1](CJ) + X) 로 갱신한다.

 

dp[0][N-1], dp[1][N-1] 중 최소값이 정답이 된다.

 

시간, 공간 복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm-python/blob/main/Algorithm/codejam/2020/QR/2.%20Moons%20and%20Umbrellas.py