[python] 백준 2579 계단 오르기

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

2579번: 계단 오르기

import sys
N=int(input())

# stairs 에 각 숫자 입력
stairs=[]

#stairs_point 에 n1/n2/n3 에 대한 정보를 넣을 예정
stairs_point = [[0,0,0] for _ in range(N)] 

for _ in range(N):
    stairs.append(int(sys.stdin.readline().strip()))

stairs_point[0][0] = stairs[0]
stairs_point[0][1] = stairs[0]

for i in range(1,N): # i 는 1 부터 N-1 까지 ( 이러면 맨 첫번째 케이스는 따로 분류)
    # n1 case 계산
    stairs_point[i][0] = stairs_point[i-1][1] + stairs[i]

    # n2 case 계산 
    stairs_point[i][1] = stairs_point[i-1][2] + stairs[i]

    # n3 case 계산
    stairs_point[i][2] = max(stairs_point[i-1][0] ,stairs_point[i-1][1] )
answer = max(stairs_point[N-1][0] , stairs_point[N-1][1])
print(answer)

처음 답안이다 

 

 

 

 

구상 할때 쓴 엑셀이다. bottom-up 을 사용하기로 정했고 그렇게된다면 case 는 3가지가 나올 수 있다.

위의 사진에서 처럼 n1,n2,n3 의 경우가 나올 수 있다. 

그런식으로 a(n) 의 n1/n2/n3 를 구한 후에 a(n+1) 을 구하려고 하면 전에 해결했던 a(n) 의 n1/n2/n3 의 case 들을 가져다가 사용해주기만 하면 된다. 

 

왜 a(n+1) 을 구할 때 전(a(n)) 의 n1/n2/n3 을 case 별로 따로 생각했는지는 스스로 생각해보길 바란다( 몇개만 그려봐도 직관적으로 알 수 있다.)

 

언제나 그렇듯이 다른사람의 코드들이 내 코드보다 기하급수적으로 짧았다(...).

 

<문제점?>

이문제는 다이나믹 프로그래밍을 사용해야하는 문제였는데 내가 푼 방식은 다이나믹 프로그래밍을 완벽하게 사용하지 못하는 느낌이 들었다. 그이유를 설명해보자면

 

1. 큰 문제를 작은 문제로

큰 문제를 작은 문제로 나눈 것 까지는 맞다. 하지만 작은 문제에서의 최적의 해가 큰 문제의 해까지 꼭 연결되지 않은 부분들이 존재했다.

 

2. bottom-up

나름 바텀업 방식을 사용하려고 했는데 ( 하긴했지만 ) case 를 3가지로 나눈다는 것 자체가 다이나믹 프로그래밍보다는 그냥 수학적인 방식으로 코드를 풀어낸 게 아닌가.. 하는 생각이 들었다. 

 

--> 다시 확인해 보니까 bottom-up 방식으로 다이나믹 프로그래밍을 사용한 것은 맞았고 top-bottom 형식을 사용해서 구할 수도 있었다.

bottom-up  :  반복문을 이용

top - bottom : 재귀를 이용

반복문을 이용하는게 재귀를 이용 하는 것 보다 빠르다

재귀를 이용하면 더 직관적으로 코드를 짤 수 있다는 이점이 있다. 

 

다른 사람의 코드를 리뷰해 보면서 어디서 더 예쁘게 표현할 수 있는지 알아보겠다. 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

다른 타 블로그의 코드들을 살펴 보면 나는 경우의 수를 3가지로 나누었는데

다른 풀이들에 의하면 경우의 수를 2가지로만 나누어도 문제들을 해결 할 수 있었다. 

그중에서 이 코드를 가지고 설명해 보자면..

 

https://wtg-study.tistory.com/76

[C언어] 백준 2579 : 계단 오르기

 

다른 풀이들 여러개를 살펴보았는데 대체적으로 이런 방식이였다. 

문제 조건에 마지막 계단은 무조건 도착해야 한다고 했으니

 

n번째 계단을 꼭 밟는다고 생각하고 그걸 f(n)이라고 가정한다면

 

f(n) --> 현재 층에서 최고의 값

g(n) --> n번째 계단의 값

 

f(n) = g(n) + max(f(n-3)+g(n-1) , f(n-2))

이런식으로 구성하면 

 

마지막 계단은 밟으면 

case1 ) 그전에 계단을 밟는 경우 ( f(n-3) + g(n-1)) / 3개는 연속으로 밟을 수 없기 때문에 한칸 띄운다.

case2)  그전 계단을 밟지 않는 경우 ( f(n-2) ) / 이렇게 되면 f(n-2) 는 n-2 번째 계단을 밟기 때문에 복잡하게 생각하지 않을 수있다. 

 

이렇게 2가지 경우로만 나눠서 생각 할 수 있게 된다. 

나는 3가지 경우르 나눠서 생각했는데 이렇게 포인트인 '' 마지막 경우를 꼭 밟는다 ''

이 조건에 초점을 맞춰서 함수를 생성하니까 조금더 간결 해 질 수 있다 .