백준 21318[자바] java 피아노 체조

문제 링크: https://www.acmicpc.net/problem/21318

21318번: 피아노 체조

▶문제

피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다.

시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i < y)번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 한다. 특히, 마지막으로 연주하는 y번 악보에선 절대 실수하지 않는다. 시은이는 오늘도 피아노 체조를 하기 위해 두 정수 x와 y를 골랐고, 문득 궁금한 것이 생겼다. 오늘 할 피아노 체조에서 실수하는 곡은 몇 개나 될까?

▶입력

첫 번째 줄에 악보의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

두 번째 줄에 1번 악보부터 N번 악보까지의 난이도가 공백을 구분으로 주어진다.

세 번째 줄에 질문의 개수 Q(1 ≤ Q ≤ 100,000)이 주어진다.

다음 Q개의 줄에 각 줄마다 두 개의 정수 x, y(1 ≤ x ≤ y ≤ N)가 주어진다.

▶출력

x번부터 y번까지의 악보를 순서대로 연주할 때, 몇 개의 악보에서 실수하게 될지 0 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.

▶해설

누적합을 이용해서 풀 수 있는 문제입니다. 조건을 살펴보겠습니다. 

 

1. 현재 난이도가 다음 난이도보다 높으면 실수를 한다.

2. 마지막곡은 실수하지 않는다. 

 

N=1~100000, M=1~100000 이므로 값이 들어올때마다 값을 계산한다면, 시간 초과가 발생합니다. 따라서 이전까지 실수가 발생한 횟수를 더하면서 N까지 가면됩니다.

 

index는 1부터 시작

arr: 난이도 배열

sum: 실수한 누적 회수를 더한 배열

ex) 1 2 3 3 4 1 10 8 1

 

index = 1

0>1 false -> sum[1]= sum[0]

 

index = 2

1>2 false -> sum[2]=sum[1]

 

index = 3

2>3 false -> sum[3]=sum[2]

 

index = 4

3>3 false -> sum[4]=sum[3]

 

index = 5 

3>4 false -> sum[5]=sum[4]

 

index = 6

4>1 true -> sum[6] = sum[5]+1

 

index = 7

1>10 false -> sum[7] = sum[6]

String[] s = br.readLine().split(" ");
for (int i = 1; i <= n; i++) {
    arr[i] = Integer.parseInt(s[i - 1]);
    if(arr[i-1]>arr[i]){
        sum[i] += sum[i-1]+1;
    }else{
        sum[i] = sum[i-1];
    }
}

 

위와 같이 만약 현재의 값과 이전 값을 비교했을 때 이전 값이 더 크다면 이전까지 누적된 실수 회수 +1을 진행합니다.

반대로 현재 값이 이전값과 같거나 크다면, 이전의 실수 회수를 그대로 가져옵니다. 

 

그 후 구간이 주어졌을 때 sum[end] - sum[start]를 하면 정답이 출력됩니다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static int n, m, mistake;
    static int[] arr;
    static int[] sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n + 1];
        sum = new int[n + 1];

        String[] s = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(s[i - 1]);
            if(arr[i-1]>arr[i]){
                sum[i] += sum[i-1]+1;
            }else{
                sum[i] = sum[i-1];
            }
        }

        m = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        int start, end;
        for (int i = 0; i < m; i++) {
            String[] s1 = br.readLine().split(" ");
            start = Integer.parseInt(s1[0]);
            end = Integer.parseInt(s1[1]);
            sb.append(sum[end]-sum[start]).append("\n");
            mistake=0;
        }
        System.out.println(sb.toString());
    }
}