[KOI 초등부] BOJ 17608 막대기 (2019 1차 대회)

불러오는 중입니다...

문제 유형 :  개인적으론 ad-hoc인듯

 

해설 : 

먼저 막대기의 길이를 배열에 저장, 막대기의 개수가 N이라고 했을때 오른쪽에서 바라보므로 N-1, N-2, ... , 0 이렇게 마지막 원소부터 차례대로 순회를 하는데, "지금까지 순회한 막대기 중 가장 긴 것"보다 길이가 긴 경우에만 개수를 더해주면 된다. 지금까지 순회한 막대기 중 가장 큰 것 보다 작거나 같은 경우는 눈에 보이지 않기 때문

 

문제의 테스트 케이스를 직접 그려보면 이해가 잘 된다.

 

구현 :

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	public class Main {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());
	int arr[] = new int[N+1];
	for(int i = 0; i < N; i++) {
	arr[i] = Integer.parseInt(br.readLine());
	}
	int max = 0;
	int ans = 0;
	for(int i = N-1; i >= 0; i--) {
	if(arr[i] > max) {
	ans++;
	max = Math.max(min, arr[i]);
	}
	}
	System.out.println(ans);
	br.close();
	}
	}

view raw BOJ_17608.java hosted with ❤ by GitHub