[BOJ] 백준 21318. 피아노 체조

🥈 피아노 체조

https://www.acmicpc.net/problem/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 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.

💡 아이디어

그려서 생각하니 편했다.

누적합 문제라고는 하는데, 누적합 문제를 특별히 푸는 법이 있는지 잘 몰라서 그냥 완전탐색으로 풀었다.

❗ 시간초과난 코드 - 이중for문

#피아노체조 
n = int(input())
nl = list(map(int, input().split()))
    
q = int(input())

for i in range(q):
    x, y = map(int, input().split())
    # x 부터 y 까지 j가 j+1 보다 크면 카운트한다
    count = 0 
    tmp = nl[x-1] #시작점
    for j in range(x-1,y):
        if nl[j] < tmp: #앞에것이 더 크면 카운트 증가
            count += 1
        tmp = nl[j]
        
    print(count)

역시나! 꽤나 쉬운데 왜 실1이지? 생각했는데,

Q가 10만까지 가능하다보니 시간초과가 당연히 났다 ㅎㅎ

2중포문을 안쓰는 방향으로 문제를 풀어야 해결할 수 있을것 같다.

---

🆙 통과된 풀이

주어진 1 2 3 3 4 1 10 8 1 을 통째로 두고 실수하는 횟수를 생각해보면

4-1, 10-8, 8-1 부분에서 실수가 난다

실수 배열을 만들면 이렇게 쓸 수 있다. 0 0 0 0 0 1 1 2 3

이때 특정 구간에서 일어나는 실수를 구하려면 끝 - 시작을 빼주면 된다

#피아노체조 
import sys
input = sys.stdin.readline
n = int(input())
nl = list(map(int, input().split()))
mis = [0] * n
for i in range(1, n):
    if nl[i-1] > nl[i]: # 전꺼가 더 크다면 
        mis[i] = mis[i-1] + 1 # mis[i]는 전의 실수 + 1
    else: 
        mis[i] = mis[i-1] # 아니라면 직전것과 같은 실수
        
q = int(input())
for j in range(q):
    x, y = map(int,input().split())
    print(mis[y-1] - mis[x-1])

🍎 느낀점

✅ import sys input = sys.stdin.readline 이거 안쓰면 시간초과난다

✅ 완탐대신 누적합!