AOJ 2243: ダンレボのあれ

問題

Step Step Evolution | Aizu Online Judge

上の図の一番右のように右足と左足が交差しないようにパネルを踏む時、同じ足で連続して踏む回数を最小にするにはどうしたら良いか。

解法

DP。例えば、i番目のパネルがi-1番目のパネルより右にある時、i番目までで連続して踏んだ回数dp[i][右]は、

dp[i][右] = Math.min(dp[i - 1][左], dp[i - 1][右] + 1);

のように書ける。また、i番目のパネルがi-1番目のパネルより右にある時はi番目のパネルを左で踏むことは絶対にないので、dp[i][左]には十分大きい値を入れて弾いておく。

コード

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        while (true) {
            String steps = scan.next();
            if (steps.equals("#")) {
                scan.close();
                break;
            }
            int N = steps.length();
            int[] table = new int[N];
            for (int i = 0; i < table.length; i++) {
                table[i] = Character.getNumericValue(steps.charAt(i));
            }
            // i文字目をkで踏んだ時の踏める回数
            // 右の時k=0、左の時k=1
            int[][] dp = new int[N][2];

            for (int i = 1; i < N; i++) {
                if ((table[i] - 1) % 3 > (table[i - 1] - 1) % 3) {
                    // i-1番目が左だったらセーフ
                    // i番目がi-1番目より右だった時
                    dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][0] + 1);
                    dp[i][1] = Integer.MAX_VALUE - 1;// 左で踏むことは絶対にない
                } else if ((table[i] - 1) % 3 < (table[i - 1] - 1) % 3) {
                    // i番目がi-1番目より左だった時
                    dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1] + 1);
                    dp[i][0] = Integer.MAX_VALUE - 1;
                } else {
                    dp[i][1] = dp[i - 1][0];
                    dp[i][0] = dp[i - 1][1];
                }
            }

            System.out.println(Math.min(dp[N - 1][0], dp[N - 1][1]));
        }

    }
}