[백준] 피아노 체조(python)(누적합)

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

21318번: 피아노 체조

 

1. 난이도 실버1 (🥈) 

 

2. 문제 해결 방법

 

누적합을 이용해서 문제를 해결하면 된다.

 

지금 연주가 다음 연주보다 어려울 경우 '총 실수'에서 +1 해준 값으로 list의 value를 바꿔준다.

 

이후 주어진 구간의 합을 출력하면 된다.

 

 

 

//실수한 부분//

 

'마지막 연주는 무조건 실수하지 않는다'를 분리해서 생각해

 

1. 실수를 한 횟수가 누적된 list

2. 지금 연주가 다음보다 더 어려운 인덱스가 저장된 list를 두 개 만들어서 문제를 풀었다.

 

그러나 어차피 마지막 연주는 고려하지 않아도 되기 때문에

 

'실수를 한 횟수가 누적된 list'에서 구간합을 구할 때, right-1을 해주거나

전체 answer에서 1을 해주면 된다는 것을 깨닫고 수정했다.

 

 3. 내가 작성한 코드

import sys
input = sys.stdin.readline

n = int(input().rstrip()) #악보의 개수
music = list(map(int, input().rstrip().split())) + [0] #실수가 누적된 list
level = [0] * (n+1) #실수를 하게되는 index

temp = 0

for i in range(n): 
  if music[i] > music[i+1]: #지금 연주가 다음 연주보다 어려울 경우
    level[i] = 1
    temp += 1 #실수 누적
  music[i] = temp

for _ in range(int(input())):
  left, right = map(int, input().rstrip().split())
  
  answer = music[right-1] - music[left-2]

  if level[right-1]: 
    answer -= 1

  print(answer)

 

 

4. 수정 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip()) #악보의 개수

music = list(map(int, input().rstrip().split())) + [0] #실수의 누적합

temp = 0

for i in range(n):
  if music[i] > music[i+1]: #지금 연주가 다음 연주보다 어려우면 실수 누적
    temp += 1
  music[i] = temp

for _ in range(int(input())): #구간합 출력
  left, right = map(int, input().rstrip().split())
  print(music[right-2] - music[left-2])