[실버 III] 2579번. 계단 오르기

 문제 

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

2579번: 계단 오르기

 사용 언어 

Python3

 풀이 과정 

또다른 동적계획법 문제이다. 동적계획법 문제가 진짜 많은 것 같다.

계단을 한 칸 오르거나 두 칸 오를 수 있으므로 두 가지 중에 더 큰 값을 넣어주는 것은 당연했는데,

max(두 칸 전과 현재 칸을 더한 것 / 세 칸 전과 이전 칸, 현재 칸을 더한 것)을 생각해내는 게 좀 어려웠다.

 

그리고 처음에는 런타임 에러가 떴다. 보통 런타임 에러는 간단하게 프로그램이 비정상적으로 종료된 경우인데, 내가 맞다고 생각해서 제출한 코드가 런타임 에러가 뜬 것은 처음이라 당황했다.

from sys import stdin
input = stdin.readline

stairs = int(input())
scores = [int(input()) for _ in range(stairs)]

dp = [0] * stairs # 해당 계단을 밟을 때까지 얻을 수 있는 최대 점수
dp[0] = scores[0]
dp[1] = scores[0] + scores[1]
dp[2] = max(scores[0] + scores[2], scores[1] + scores[2])

for i in range(3, stairs):
    dp[i] = max(dp[i-2] + scores[i], dp[i-3] + scores[i] + scores[i-1])

print(dp[-1])

그래서 알아보니 파이썬에서 런타임 에러가 뜨는 데엔 다양한 이유가 있지만 없는 인덱스를 참조할 때 주로 에러가 난다는 사실을 알았다. 그걸 알고 코드를 보니까 보이는 에러 부분. 위와 같이 짜면 입력값이 1이나 2일 때는 오류가 나는 것이었다.

 

그걸 깨닫고 간단하게 수정해줬더니 맞았습니다!!

 제출 답안 

from sys import stdin
input = stdin.readline

stairs = int(input())
scores = [int(input()) for _ in range(stairs)]

dp = [0] * stairs
if stairs < 3:
    print(sum(scores))
else:
    dp[0] = scores[0]
    dp[1] = scores[0] + scores[1]
    dp[2] = max(scores[0] + scores[2], scores[1] + scores[2])

    for i in range(3, stairs):
        dp[i] = max(dp[i-2] + scores[i], dp[i-3] + scores[i] + scores[i-1])

    print(dp[-1])

 공부한 내용 

파이썬의 런타임 에러

파이썬에서 런타임 에러가 나는 경우는 다양하다. 따라서 아래와 같이 정리해봤다. 자세한 내용을 확인하기 위해서는 출처를 참고하자.

 

1. 배열에 할당된 크기를 넘어서 접근했을 때
2. 전역 배열의 크기가 메모리 제한을 초과할 때
3. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
4. 0으로 나눌 떄
5. 라이브러리에서 예외를 발생시켰을 때
6. 재귀 호출이 너무 깊어질 때
7. 이미 해제된 메모리를 또 참조할 때
8. 프로그램(main 함수)이 0이 아닌 수를 반환했을 때

 

출처: https://www.secmem.org/blog/2020/09/19/rte/

 코드 개선 

1. 먼저 저번 시간(?)에 배운  if __name__ == "__main__":  을 추가해보았다.

➡ 한 줄을 추가했을 뿐인데 연산량이 좀 있는 코드라 그런지 꽤 유의미한 차이를 보였다.

 

2. 그리고 이번에 시도해 본 try ~ catch문으로 입력값 검증하기를 그냥 len으로 변경했다.

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    while True:
        Input = input().split()
        if len(Input) == 1:
            break

➡ 아무래도 try ~ catch에서 오류를 처리하는 과정이 더 오래 걸릴 것 같아 바꿔봤는데 또 조금 줄어들었다.

 

3. values( )에서 1번 걸린 경우를 추출하는 것도 시간이 좀 걸리지 않을까 싶어서 변수 하나에 +- 하는 로직을 추가해봤다.

justOnetime = 1
        while True:
            x = (((a % N) * (((x % N) * (x % N)) % N)) % N + (b % N)) % N
            if x in playing:
                playing[x] += 1
                if playing[x] == 2:
                    justOnetime -= 1
                if playing[x] == 3:
                    break
            else:
                playing[x] = 1
                justOnetime += 1

➡ 그랬더니 지금까지 중 제일 오래걸렸다...! 연산량이 많다 보니까 마지막에 한 번만 계산하는게 훨씬 낫나 보다.

 

4. 그러고 나서 생각해보니 내가 과하게 분배법칙으로 늘려놓은 모듈러 연산이 생각났다. 그래서 그 연산을 조금 더 간결하게 줄였다.

전 : (((a % N) * (((x % N) * (x % N)) % N)) % N + (b % N)) % N
후 : (((a * x) % N) * (x % N) + b) % N

➡ 가장 유의미한 변화가!! ㅋㅋㅋㅋㅋㅋㅋㅋ 괜히 늘리고 늘렸자나... 괄호 갯수 머리아팠는데....

 

---

어쨌든 여기까지 개선하고  맞힌 사람 을 봤더니

흐히히흐힣 기분좋아✨ 짜릿해⚡