[BOJ/Python] 2579. 계단 오르기

📌 문제

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

2579번: 계단 오르기

 

📌 문제 접근 방법

1. 첫 번째 칸을 밟는 경우, 최대값은 첫 번째 칸의 점수
2. 두 번째 칸을 밟는 경우, 최대값은 첫 번째 칸 + 두 번째 칸의 점수
3. 세 번째 칸을 밟는 경우,
   첫 번째 칸 + (2칸 이동) 세 번째 칸
   두 번째 칸 + (1칸 이동) 세 번째 칸
4. i번째 칸을 밟는 경우,
   i-3번째 칸 + (2칸 이동) i-1번째 칸 + (1칸 이동) i번째 칸
   i-2번째 칸 + (1칸 이동) i번째 칸
5. 위의 점화식을 코드로 구현해준다!
6. 다만, 처음에는 score와 max_score 리스트를 
   

   score = [0] + [int(input()) for _ in range(N)]
   max_score = [0 for _ in range(N+1)]

   이렇게 N+1 만큼으로 잡아줬는데, 이 경우에 N이 1이 들어온다면 인덱스 에러가 발생한다.
   

   max_score[1] = score[1]
   max_score[2] = score[1]+score[2]
   max_score[3] = max(score[1]+score[3], score[2]+score[3])​

   이 부분에서!
7. 따라서 처음부터 N의 최대값인 300을 대입해서 리스트를 만들어주고 반복문으로 입력을 받아준다.

 

이거 대체 왜 실버3인지...?

 

📌 코드

N = int(input())

score = [0]
for _ in range(N):
    score.append(int(input()))

# 두 칸 이동하는 경우 인덱스 에러가 나지 않도록 뒤에 2개의 인덱스를 더 생성
# 인덱스의 숫자를 맞추기 위하여 앞에 1개의 인덱스를 더 생성
arr = [0 for _ in range(N+3)]

for i in range(N, -1, -1):
    # 마지막 칸은 무조건 밟아야 함
    if i == N:
        arr[i] = score[i]
    
    # 한 칸 이동하는 경우 : 그 전 이동은 무조건 2칸 이동이여야 함
    arr[i-1] = max(arr[i-1], arr[i+2] + score[i] + score[i-1])

    # 두 칸 이동하는 경우 : 그 전 이동이 어떤 경우이든 상관없음! 무조건 최대값에 점수 더해주기
    arr[i-2] = max(arr[i-2], arr[i] + score[i-2])

print(arr[1])

첫 번째 아이디어

1. 마지막 계단은 어차피 밟아야 한다! → 뒤에서부터 생각해보자
2. 마지막 계단에서 한 칸 또는 두 칸 내려올 수 있다.
   두 가지 경우 중에서 더 점수가 큰 칸으로 내려오기!
3. 만약 현재 있는 칸의 다음 칸에 점수가 채워져있다면, 이 경우에는 2칸 이동만 가능하다.

[실패] : 연속으로 3칸을 밟는 경우를 찾아내지 못한다.

 

def up_higher(now, score, cnt):
    # cnt : 연속으로 1칸 오른 횟수
    global max_score

    if now == N:
        max_score = max(max_score, score)
        return
    
    if now+1 <= N and cnt != 1:
        # 한 칸 오르는 경우
        up_higher(now+1, score+scores[now+1], cnt+1)

    # 두 칸 오르는 경우
    if now+2 <= N:
        up_higher(now+2, score+scores[now+2], 0)


N = int(input())
scores = [0] + [int(input()) for _ in range(N)]

max_score = 0
up_higher(0, 0, -1)

print(max_score)

두 번째 아이디어

재귀로 구현해보자!

[실패] : 시간초과

 

N = int(input())
score = [0 for _ in range(301)]
max_score = [0 for _ in range(301)]

for i in range(N):
    score[i+1] = int(input())

max_score[1] = score[1]
max_score[2] = score[1]+score[2]
max_score[3] = max(score[2]+score[3], score[1]+score[3]) # 한 칸 이동, 두 칸 이동

for i in range(4, N+1):
    max_score[i] = max(max_score[i-3]+score[i-1]+score[i], max_score[i-2]+score[i]) # 한 칸 이동, 두 칸 이동

print(max_score[N])

세 번째 아이디어

결국 구선생님의 힘을 빌려서 성공...!