백준 22114번: 창영이와 점프

문제 설명

• https://www.acmicpc.net/problem/22114

접근법

• 점프를 사용한 횟수를 행으로 하는 2차원 배열을 만들어 문제를 해결할 수 있습니다. dp[i][j] = 점프를 i번 뛴 상태로 j에 도달했을 때 연속으로 밟은 블록의 최댓값
  • i블럭에서 i+1블럭으로 이동할 수 있다면
    • dp[0][i] = dp[0][i-1]+1 - 이동
    • dp[1][i] = dp[1][i-1]+1 - 이동
  • i블럭에서 i+1블럭으로 이동할 수 없다면
    • dp[0][i] = 1 - 처음부터 다시시작
    • dp[1][i] = dp[0][i-1]+1 - 점프 사용
• 마지막 돌이 반드시 정답에 포함된다는 보장이 없습니다. 그러므로 각 돌에 대해 모두 최댓값 검사를 해야 합니다.

정답

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
		for (int i = 1; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int answer = 0;
		int[][] dp = new int[2][N];
		dp[0][0] = 1;
		dp[1][0] = 1;
		for (int j = 1; j < N; j++) {
			if(arr[j] <= K) {
				dp[0][j] = dp[0][j-1]+1;
				dp[1][j] = dp[1][j-1]+1;
			} else {
				dp[0][j] = 1;
				dp[1][j] = Math.max(dp[0][j-1]+1,1);
				
			}
            // 모든 j에 대해 최댓값 검사
			answer = Math.max(answer, Math.max(dp[0][j], dp[1][j]));
		}
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		System.out.println(answer);
	}

}