[Python] BOJ 21318 - 피아노 체조

www.acmicpc.net/problem/21318

G번: 피아노 체조

단순히 수학문제여서 정석대로 풀었다가 혼쭐난 문제이다.

 

1. 처음에 그냥 for문으로 hard배열(난이도)를 돌면서 현재 난이도가 다음 난이도보다 높으면

miss에 1을 더해주고 miss를 return 해주는 식으로 풀었다.

import sys
input = sys.stdin.readline
N = int(input())
hard = list(map(int,input().split()))
def mistake(x, y):
	miss = 0
	for i in range(x-1, y-1):
		if hard[i] > hard[i+1]:
			miss += 1
	return miss

for _ in range(int(input())):
	x, y = map(int,input().split())
	print(mistake(x, y))

결과는 바로 시간초과 (pypy3에 빠른 입출력을 썼는데도)

아무래도 Q가 10만이고 mistake함수에서도 for문을 y-x번(최대 10만) 돌기때문에 O(10만 x 10만)이어서 안되는 듯하다.

 

2. 그냥 처음부터 hard배열을 받고 hard배열 안에서 현재 난이도가 다음 난이도보다 높으면 1 아니면 0을 넣어주었다.

   마지막엔 실수가 없으므로 hard[N-1]에는 0을 넣어주고

   입력받은 x와 y사이의 sum을 print해주는 식으로 풀었다.

import sys
input = sys.stdin.readline
N = int(input())
hard = list(map(int,input().split()))
for i in range(N-1):
	hard[i] = 1 if hard[i] > hard[i+1] else 0
hard[N-1] = 0
for _ in range(int(input())):
	x, y = map(int,input().split())
	print(sum(hard[x-1:y-1]))

결국 sum함수 또한 O(N)이므로 또 시간초과가 떴다...

 

3. 몇분 동안 또 머리를 싸맨 결과, 그냥 s라는 1부터 i번째까지의 실수 횟수를 누적해서 더해주는 배열을 만들었다. 

   ex) 입력이 1 2 3 3 4 1 10 8 1이면 s는 [0, 0, 0, 0, 0, 1, 1, 2, 3]이다. (5번째, 7번째, 8번째에서 실수를 하므로)

   그 뒤 바로 s[y-1] - s[x-1]을 통해 O(1)에 답을 구할 수 있게 했다.

import sys
input = sys.stdin.readline
N = int(input())
hard = list(map(int,input().split()))
s = [0] * N
for i in range(1, N):
	s[i] = s[i-1]+1 if hard[i-1] > hard[i] else s[i-1]
for _ in range(int(input())):
	x, y = map(int,input().split())
	print(s[y-1] - s[x-1])

드디어 통과..

(solved.ac 티어: 실버 1)