[백준온라인] 22114번 창영이와 점프

문제 : https://www.acmicpc.net/problem/22114

22114번: 창영이와 점프

문제 요약 : 최대로 밟을 수 있는 블록 개수 출력

입력	출력
2 ≤ N(블럭 개수) ≤ 100000 1 ≤ K(보폭), L(블럭 사이 거리) ≤ 100	임의의 점프를 한번 할 수 있을 때 최대로 밟을 수 있는 블럭 개수 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_22114.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
30869039	cbkpar	22114	맞았습니다!!	26132KB	316ms	Java 11	929B

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,k,i,m;
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for(i=0;i<n-1;i++) arr[i] = Integer.parseInt(st.nextToken());
		int[][] dp = new int[n][2];
		dp[0][0] = dp[0][1] = 1;
		for(i=0;i<n-1;i++) {
			if(arr[i]<=k) {
				dp[i+1][0] = dp[i][0] + 1;
				dp[i+1][1] = dp[i][1] + 1;
			}else {
				dp[i+1][0] = 1;
				dp[i+1][1] = dp[i][0] + 1;
			}
		}
		m = 0;
		for(i=0;i<n;i++) {
			m = Math.max(m, dp[i][0]);
			m = Math.max(m, dp[i][1]);
		}
		System.out.println(m);
	}
}

밟은 블럭의 개수를 점프를 사용했는지와 안 했는지로 구분한다.

초기값을 1로 둔 뒤에 블럭을 다음과 같이 차례대로 계산한다.

 

블럭 사이의 거리가 보폭보다 같거나 짧은 경우

점프 미사용[i] = 점프 미사용[i-1] + 1

점프 사용[i] = 점프 사용[i-1] = 1

 

블럭 사이의 거리가 보폭보다 클 경우

점프 미사용[i] = 1

점프 사용[i] = 점프 미사용[i-1] + 1

 

그 후 배열의 가장 큰 값을 출력하면 된다.

 

예제 ) 

7 3

2 3 1 5 3 3