Submission #1413089

---

Source Code Expand

import java.util.*;

public class Main {

    static int N;
    static int dp[];
    static String r;
    // static int dfs(int k){
    //     int tmp = 99999999;
    //     int flag = 0;
    //     if(k<0) return 0;
    //     if(r.charAt(k) == 'X') flag = 1;
    //     for(int i = 1; i < 4; i++){
    //         tmp = Math.min(tmp, dfs(k-i)+flag);
    //     }
    //     return dp[k] = tmp;
    // }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); //区間数
        r = sc.next(); //道路の状況
        dp = new int[N];
        for(int i = 0; i < N; i++){
            dp[i] = 0;
        }
        dp[0] = 0;
        for(int i = 1; i < N; i++) {
            int flag = 0;
            int tmp = 999999;
            if(r.charAt(i) == 'X') flag = 1;
            for(int j = 1; j <= 3; j++){
                if(i-j>=0) tmp = Math.min(tmp, dp[i - j]+flag);
                dp[i] = tmp;
            }
        }
        System.out.println(dp[N-1]);
    }
}

Submission Info

Judge Result