[Python] BOJ 21318 - 피아노 체조
728x90
반응형
단순히 수학문제여서 정석대로 풀었다가 혼쭐난 문제이다.
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)
728x90
반응형
'문제풀이 > BaekjoonOnlineJudge' 카테고리의 다른 글
[Python] BOJ 7569 - 토마토(BFS) (0) | 2021.03.28 |
---|---|
[Python] BOJ 21316 - 스피카 (0) | 2021.03.28 |
[Python] BOJ 18291 - 비요뜨의 징검다리 건너기 (0) | 2021.03.24 |
[Python] BOJ 1520 - 내리막 길(DFS + DP) (0) | 2021.03.24 |
[Python] BOJ 2667 - 단지번호붙이기(DFS) (0) | 2021.03.23 |
TAGS.