[백준 / python] #17608. 막대기

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

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])

성공하였다.