Submission #148408

---

Source Code Expand

import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		new Main().run();
	}

	void run()
	{
		Scanner cin = new Scanner(System.in);
		N = cin.nextInt();
		S = cin.next();
		dp = new int[N];
		//予め-1で初期化する
		for(int i=0;i<N;i++) dp[i] = -1;
		//探索で求めた答えを出力
		System.out.println(dfs(0));
	}

	String S;
	int N;
	int[] dp;

	int dfs(int k){
		if(k >= N - 1) return 0;
		if(dp[k] != -1) return dp[k];
		int ret = 99999999;
		int temp = 0;
		//その地点が水たまりなら、回数を1増やす
		if(S.charAt(k) == 'X') temp = 1;
		//1から3の3種類の探索を行う
		for(int i=1;i<=3;i++){
			ret = Math.min(ret, dfs(k+i) + temp);
		}
		return dp[k] = ret;
	}
}

Submission Info

Judge Result