백준 21318번: 피아노 체조 [누적합][구간합] -Java

https://www.acmicpc.net/problem/21318

21318번: 피아노 체조

피아노 치고 싶당

시간복잡도가 0.5초라도 되어있지만.. 하기 코드는 O(1)이라 무관.. 최대 100,000이다

 

<백준 21318번 피아노체조 정답 Java코드>

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

public class Boj21318 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int music[] = new int[N+1];
		int mis[] = new int[N+1]; 
		for (int i = 1; i <= N; i++) {
			int num = Integer.parseInt(st.nextToken());
			music[i] = num;
			if(num<music[i-1]) // 내 앞곡이 더 난이도가 높으면?
				mis[i-1]++;
			
			mis[i] = mis[i-1];
		}
		
//		for (int i = 0; i < mis.length; i++) {
//			System.out.print(mis[i]+"\t");
//			
//		}
//		System.out.println();
		
		//범위 받고 계산
		st = new StringTokenizer(br.readLine());
		int Q = Integer.parseInt(st.nextToken());
		
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			int res = mis[y-1]-mis[x-1]; //마지막 곡은 항상 실수가 없으니 제외하고 범위계산
			System.out.println(res);
		}

	}

}