[CodeUp] 4564번 : 계단 오르기 (Python)

Python

방법 1 - 메모리 27724 / 시간 19 / 코드 길이 301B

가장 일반적인 풀이이고 이 방법은 재귀로 푸는 것이 아니다.

가장 기본적인 아이디어는 문제를 쪼개는 것이고 쪼갤 때 특징을 잘 파악하는 것이다.

우리는 여기서 1단계 또는 2단계 점프를 할 수 밖에 없다.

그러나 1단계를 3번 밟는 것은 불가능하다.

즉, 1단계는 2번까지 하고 반드시 2단계를 밟아야한다.

그리고 2단계를 하고 나서는 다시 일종의 초기화로 보면된다.

본 문제풀이는 buttom up 방식으로 아래에서부터 위로 점진적으로 올라가는 것을 채택한다.

이렇게 하면 dp라는 일종의 memorization이 됨과 동시에 원하는 곳까지 순차적으로 올라간다.

다만 제일 중요한 아이디어는 max(dp[i-3] + a[i] + a[i-1], dp[i-2]+a[i])이다.

순서가 모호해서 그런데 우리가 i가 6이라는 것을 넣고 숫자로 표현해보겠다.

dp[6] = max(a[6] + a[5] + dp[3], a[6] + a[4])이다.

앞부분부터 살펴보면 숫자가 6,5,3이다.

즉, 3번째 위치까지 도달하는 최대값 dp[3]에서 시작해서 2칸을 뛰어 5번째에 도달하고 6번째에 도달한다는 의미이다.

3까지 어떻게 도달했는지는 상관없다. 왜냐하면 바로 2칸을 뛰기 때문이다.

뒷 부분을 보면 숫자가 6,4이다.

즉, 4번째 위치까지 도달하는 최대값 dp[4]에서 시작해서 2칸을 뛰어 6번째에 도달한다는 의미이다.

이 역시 4까지 어떻게 도달했는지는 상관없다. 왜냐하면 바로 2칸을 뛰기 때문이다.

총 정리해보면 6에 도달하는 가장 큰 값을 도달하는 방법은 크게 2가지가 있고 이는 2점프 후 1단이거나 2단 점프 후 도달하는 것이다.

def s(n, a):
  dp = []
  dp.append(a[0])
  dp.append(a[0]+a[1])
  dp.append(max(dp[0]+a[2],a[1]+a[2]))
  
  for i in range(3, n):
    dp.append(max(dp[i-3]+a[i]+a[i-1], dp[i-2]+a[i]))
  return dp

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

print(s(n, a)[-1])

방법 2 - 메모리 27724 / 시간 19 / 코드 길이 441B

재귀를 통한 방법

재귀를 위한 초기값 설정이 필요하고 memorization을 위한 if문을 추가하고 나머지는 방법 1과 동일하다.

방법 1은 for문으로 돌렸다면 여기서는 재귀!

약간의 차이는 Top-Buttom 방식으로 재귀를 한다는 것이다.

def s(n, a, dp):
  if n == 1:
    dp[1]=a[1]
    return dp[1]
  elif n == 2:
    dp[2]=a[1]+a[2]
    return dp[2]
  elif n==3:    
    dp[3] = max(a[1]+a[3], a[2]+a[3])    
    return dp[3]

  if dp[n]:
    pass
  else:
    dp[n]=max(s(n-3,a,dp)+a[n]+a[n-1],s(n-2,a,dp)+a[n])
  return dp[n]

n = int(input())
a = [0]
dp = [0 for _ in range(n+1)]

for i in range(1, n+1):
  a.append(int(input()))

print(s(n, a, dp))