https://www.acmicpc.net/problem/17608
문제 풀이
막대기를 리스트에 입력받고, 앞에서 뒤로 리스트를 탐색하면서 점점 더 높은 막대만 카운트하면 된다. 반복문으로 풀 수도 있을 것 같은데, 재귀 함수에 익숙해지고자 간단하지만 재귀 로직으로 구현해봤다.
구현 로직
첫 번째 시도
import sys
input = sys.stdin.readline
def go(arr, idx, cmp):
global ans
if idx >= len(arr):
print(ans)
return
if arr[idx] > cmp:
ans += 1
cmp = arr[idx]
go(arr, idx+1, cmp)
arr = list()
for _ in range(int(input())):
arr.append(int(input()))
arr.reverse()
ans = 1
go(arr, 1, arr[0])
런타임 에러가 떴다. 상세 보기를 했더니 Recursion Error라고 한다. Index Error는 종종 봤는데, Recursion Error는 처음 봤다. 이제껏 재귀를 잘 써보지 않았더니 처음 보는 것 같고, 앞으로 종종 마주치지 않을까 싶다.
이를 어떻게 해결하나 알아봤더니 백준에서 자체적으로 재귀 깊이를 제한해두었으니 이를 살짝 더 열어주면 된다고 한다. 사실 제한해둔걸 더 열어서 성공하는게 찝찝한 솔루션이라곤 생각하는데... 이런 방법도 있구나 하는 면에서 기록해두려 한다.
두 번째 시도
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) # modified
def go(arr, idx, cmp):
global ans
if idx >= len(arr):
print(ans)
return
if arr[idx] > cmp:
ans += 1
cmp = arr[idx]
go(arr, idx+1, cmp)
arr = list()
for _ in range(int(input())):
arr.append(int(input()))
arr.reverse()
ans = 1
go(arr, 1, arr[0])
성공하였다.
'Koala - 9기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[백준/python] 10062번 : 적록색약 (0) | 2023.02.24 |
---|---|
[백준/python] 15663번 : N과 M (9) (0) | 2023.02.21 |
[백준/Python] #16435 스네이크버드 (0) | 2023.02.19 |
[백준/Python] 10865번 친구 친구 (0) | 2023.02.19 |
[백준/Python] 2525번 오븐 시계 (0) | 2023.02.19 |