Submission #1417490

---

Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
	static int dp[];
	static char road[];
	static int N;

	static int dfs(int n)
	{
		if(n >= N) return 0;
		if(dp[n] != -1) return dp[n];

		int a = dfs(n + 1);
		int b = dfs(n + 2);
		int c = dfs(n + 3);
		int min = a;
		if(min > b) min = b;
		if(min > c) min = c;

		dp[n] = min + (road[n] == 'X' ? 1 : 0);

		return dp[n];
	}

	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		road = scan.next().toCharArray();
		scan.close();
		dp = new int[N];
		Arrays.fill(dp, -1);

		System.out.println(dfs(0));
	}

}

Submission Info

Judge Result