코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @Author: kbs
 */
public class Main {
    static int T, W;
    static int[] pos;

    //memo[time][moveCount][position]
    static int[][][] memo;
    static Queue<int[]> q = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        pos = new int[T + 1];
        memo = new int[T + 1][W + 1][3];

        for (int i = 0; i <= T; i++) {
            for (int j = 0; j <= W; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        //W번 옮길 수 있다.
        //높이는 T까지
        //DP랑 BFS랑 섞어볼까.
        for (int i = 1; i <= T; i++) {
            pos[i] = Integer.parseInt(br.readLine());
        }

        bfsWithMemo();

        int max = 0;

        for (int i = 0; i <= W; i++) {
            max = Math.max(memo[T][i][1], max);
            max = Math.max(memo[T][i][2], max);
        }


        System.out.println(max);
    }

    private static void bfsWithMemo() {
        q.add(new int[]{0, 0, 1});
        memo[0][0][1] = 0;
        while (!q.isEmpty()) {
            int[] current = q.poll();

            if (current[0] >= T) {
                continue;
            }

            int nextTime = current[0] + 1;
            int nextValue = memo[current[0]][current[1]][current[2]];
            if (pos[nextTime] == current[2]) nextValue += 1;

            if (memo[nextTime][current[1]][current[2]] < nextValue) {
                q.add(new int[]{nextTime, current[1], current[2]});
                memo[nextTime][current[1]][current[2]] = nextValue;
            }

            if (current[1] < W) {
                int nextPos;
                if (current[2] == 1) nextPos = 2;
                else nextPos = 1;

                nextValue = memo[current[0]][current[1]][current[2]];
                if (pos[nextTime] == nextPos) nextValue += 1;
                if (memo[nextTime][current[1] + 1][nextPos] < nextValue) {
                    q.add(new int[]{nextTime, current[1] + 1, nextPos});
                    memo[nextTime][current[1] + 1][nextPos] = nextValue;
                }
            }
        }
    }
}

bfs에 dp를 섞어보았다.