[코딩테스트][Java] 구글코드잼, Moons and Umbrellas

문제

https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1145#problem

Code Jam - Google’s Coding Competitions

 

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

 

X, Y, S가 주어질때 문자열 S의 ?에 C 또는 J를 적절히 채워서 저작권 비용을 최소로 하는 값을 구하는 문제입니다.

 

접근

문제의 타입은 동적계획법입니다. dp는 2차원 배열로 초기화합니다. 0행은 문자가 'C'일때, 1행은 문자가 'J'일때를 의미합니다. 예를 들어 dp[0][3]의 값의 의미는 3번째 문자가 'C'일때 S[0..3]까지의 최소 비용 금액을 의미합니다. 문제에 대한 순환식을 정의하면 다음과 같습니다.

수행과정

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
	
	public static long solution(int x, int y, String s)
	{
		int n = s.length();
		long[][] dp = new long[2][n];
		
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<n;j++)
			{
				dp[i][j] = Integer.MAX_VALUE;
			}
		}
		
		if(s.charAt(0)=='C' || s.charAt(0)=='?')
		{
			dp[0][0] = 0;
		}
		if(s.charAt(0)=='J' || s.charAt(0)=='?')
		{
			dp[1][0] = 0;
		}
		
		for(int i=1; i<n; i++)
		{
			if(s.charAt(i)=='C' || s.charAt(i)=='?')
			{
				// min(CC, JC+y)
				dp[0][i] = Math.min(dp[0][i-1], dp[1][i-1]+y);
			}
			if(s.charAt(i)=='J' || s.charAt(i)=='?') 
			{
				// min(JJ, CJ+x)
				dp[1][i] = Math.min(dp[1][i-1], dp[0][i-1]+x);
			}
		}
		
		return Math.min(dp[0][n-1], dp[1][n-1]);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		String[] line = null;
		int x, y;
		String s;
		for(int i=0; i<tc; i++)
		{
			line = br.readLine().split(" ");
			x = Integer.parseInt(line[0]);
			y = Integer.parseInt(line[1]);
			s = line[2];

			System.out.printf("Case #%d: %d\n",i+1,solution(x, y, s));
		}
		
	}

}

4
2 3 CJ?CC?
4 2 CJCJ
1 3 C?J
2 5 ??J???
Case #1: 5
Case #2: 10
Case #3: 1
Case #4: 0

 

References

https://withhamit.tistory.com/682