[백준] 1463 1로만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

실버 3 문제를 무턱대고 풀어봤으니 정말 심하게 혼났다..

높은 난이도는 조금더 공부하고 다시 도전해야겠다.

---

 

import sys
input=sys.stdin.readline


n=int(input())
lst=[0,0,1,1,]  	# 시간 제한이 0.15s이므로 DP를 해야함.
                	# 0 경우에는 필요없는 경우의 수이므로 0,
                	# 인덱스를 쉽게쓰기위해사용
                	# 1은 0, 2와 3은 1번 걸림(시작부분)
if n<=3:
    print(lst(n))
else:
    for num in range(4,n+1):
      if not num % 3:  	# 3으로 나눌수 있는수
          tmp = 0		# 어떤수를 추가해야할지 모르겠다.
          lst.append(tmp)
          pass
      elif not num % 2:	# 2로 나눌수 있는수
          tmp = 0		# 어떤수를 추가해야할지 모르겠다.
          lst.append(tmp)
          pass
      else: # 1을 뺀수
          lst.append(lst[-1]+1) 
          
    print(lst(n))

오래 생각하면 가능할줄 알았으나 구현에 실패했다.

이번 문제에서 생각한 부분은 시간제한이 0.15s였으므로 동적프로그래밍을 해야한다는 것이다.

소수인지 판별할때 사용하는 것처럼 아래부터 차곡차곡 쌓아가는 dp 알고리즘을 생각했다.

하지만 3으로 나누는 경우와 2로 나누는경우 그리고 1을 빼는 경우를 어떻게 구현해야할지 모르겠다.

---

타인의 코드

blog.naver.com/PostView.nhn?blogId=mengno5314&Redirect=View&logNo=222228256327&categoryNo=1&isAfterWrite=true&isMrblogPost=false&isHappyBeanLeverage=true&contentLength=12352

백준 1463 - 1로 만들기

N = int(input())

if N == 1:
    print(0)
    
elif N < 4:
    print(1)

else:

    result = [0, 0, 1, 1]
    for i in range(4, N+1):
        if not i%6:
            result.append(min(result[i//3], result[i//2], result[i-1])+1)
        elif not i%3:
            result.append(min(result[i//3], result[i-1])+1)
        elif not i%2:
            result.append(min(result[i//2], result[i-1])+1)
        else:
            result.append(result[i-1]+1)
    print(result[-1])

한 두번 봤는데도 이해를 잘 못한것이 오래 붙잡고있어도 못풀었을것이다. ㅋㅋㅋㅋ

3이나 2로 나누었을때와 1을 뺐을 때의 값 중에 가장 작은 값을 가져와서 횟수를 하나 더한 값을 결과로 받는다.

3과 2 둘다 나눠지는 경우도 생각을 못했고, 리스트에서 작은값을 가져오는 것도 생각을 못했다...

DP 관련 문제를 몇개 더 풀어보면서 더 익혀야겠다.