[파이썬 알고리즘] 백준 1463 풀이 _ 동적프로그래밍

 

 

 

처음에 보고 도무지 어떻게 풀어야 할지 모르겠다는 느낌이 들었습니다.

 

그런데 보 다보다 고민하다 보니 점화식이라는 것을 알게 됐습니다. 점! 화! 식!

계단 올라가는 거죠 10칸짜리 계단을 올라가는데 

올라갈 수 있는 방법이 세 가지라고 하는 거랑 같은 문제죠 예를 들어 2칸 올라간다, 3칸 올라간다, 1칸 내려간다

이 세가지 행동들을 최소한으로 취하여 올라가는 방법을 찾는 거조 여기서 포인트는 최소한의 횟수입니다.!

 

 

그러면 우리는 2칸짜리 계단 올라가는 것, 3칸짜리 계단 올라가는 것 등등을 계산하여

4칸짜리 계단 올라가는 문제는 2칸짜리 계단에서 2칸 올라가는 연산 한 번만 추가로 하면 최소한의 횟수로 올라가는 것을 알 수 있죠!

 

여기까지는 예시이고요 

 

우리 문제에 대한 정확한 설명과 함께 풀어보도록 하겠습니다.

 

손으로 먼저 풀고 코딩하면 좋겠네요

 

 

n=int(input())

# n-1까지의 연산횟수를 지정해줄 list를 생성합니다.
# input 숫자가 1부터 들어오기 때문에 0은 필요가 없습니다.
# input 숫자가 1이 들어올 경우만 return 값이 0입니다.
# 의미상 자기 자신의 연산횟수까지 계산 해줘야하기 때문에 n+1 길이의 list를 만들어줍니다
#원래의 의미는 1부터 n까지의 연산횟수를 저장해줘야 하는데 i의 시작은0이기 때문에 조작을 해주겠습니다.

list = [0]*(n+1)

#for i in range(1,n):
#  i=i+1
# 위의 for 구문과 같은 의미를 가지는 for문입니다.

for i in range(2,n+1):
  #2 or 3 으로도 나눠지지 않는 경우가 있기 때문에 냅다 그전 횟수에 1을 더해줍니다. 즉, -1 연산으로만 접근할수 있을때!
  
  list[i] = list[i-1]+1

# 3으로 나눠지면 1을 뺀수의 연산횟수에 1회를 더해준 수와 3으로 나눈 수의 연산횟수에 1을 더해준 수중 작은것을 고른다.
  if i%3 == 0:
    list[i] = min(list[i],list[int(i/3)]+1)
  
# 2로 나눠지면 1을 뺀수의 연산횟수에 1회를 더해준 수와 2로 나눈 수의 연산횟수에 1을 더해준 수중 작은것을 고른다.
  if i%2 == 0:
    list[i] = min(list[i],list[int(i/2)]+1)

#자기 자신 n 번째 수의 연산횟수를 return 해준다.
print(list[-1])

# 코딩을 마무리 하고 그냥 세개중에 가장 작은거 찾으면 되는거 아닌가? 하는 안일한 생각을 했습니다만, 이는 2나 3으로 나눠지지 않는 수들의 경우까지 최소를 구해버리는 것이기때문에 틀린것을 제출해보고나서 알았습니다 ㅎ
#list[i] = min(list[i-1]+1,list[int(i/3)]+1,list[int(i/2)]+1)

주저리주저리 말이 길었습니다.

 

직접 손으로 써보시고 코딩 한 줄씩 print 해보면서 확인하시는 게 역시나 이해하고 활용하는데 가장 빠를 것이라 생각합니다.