[알고리즘]BOJ_1463_1로 만들기(파이썬 for문 특정 숫자부터 시작하게 range주기, 다이나믹 프로그래밍, 리스트 생성하고 0으로 초기화하기, //로 나누기 몫 구하기)

#문제 링크

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

1463번: 1로 만들기

#문제

https://www.acmicpc.net/problem/1463
1로 만들기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.15 초 (하단 참고)	128 MB	145718	45680	28982	31.854%
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 
연산을 사용하는 횟수의 최솟값을 출력하시오.

입력
첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.

출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1
2
예제 출력 1
1
예제 입력 2
10
예제 출력 2
3

힌트
10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

 

#답안

import sys
input=sys.stdin.readline

#정수 n 입력받기
n=int(input())

#계산된 결과를 저장하기 위한 dp테이블 생성
dp = [0,0,1,1] # 0 ,1, 2, 3 의 최소 수 미리 저장

#앞서서 0,1,2,3일 경우 최소 수를 미리 저장했으므로 for문은 4부터 돌도록 한다.
for i in range(4, n+1) : #i는 4부터 n까지 돈다.
    #먼저 1을 뺄 경우 나오는 경우의 수 저장
    dp.append(dp[i-1]+1)

    #어떤 수가 2로도 나눠질 수 있고, 3으로도 나눠질 수 있으므로 if~elif구조가 아닌 if, if 구조로 가야한다. ex)6
    #2로 나누어질 경우의 수와, 먼저 1을 뺀 경우와 비교하여 min값을 다시 대입
    if i%2 == 0 :
        dp[i] = min(dp[i],dp[i//2]+1)
    #3으로 나누어질 경우의 수와, 먼저 1을 뺀 경우와 비교하여 min값을 다시 대입
    if i%3 == 0 :
        dp[i] = min(dp[i],dp[i//3]+1)

print(dp[n])

▲답안 설명

#개선답안

import sys
input=sys.stdin.readline

#정수 n 입력받기
n=int(input())

#계산된 결과를 저장하기 위한 dp테이블 생성하고 0으로 초기화
dp = [0]*(n+1)

#앞서서 0,1일 경우 최소 수는 0이므로 for문은 2부터 돌도록 한다.
for i in range(2, n+1) : #i는 2부터 n까지 돈다.
    #먼저 1을 뺄 경우 나오는 경우의 수 저장
    dp[i]=dp[i-1]+1

    #어떤 수가 2로도 나눠질 수 있고, 3으로도 나눠질 수 있으므로 if~elif구조가 아닌 if, if 구조로 가야한다. ex)6
    #2로 나누어지면서, 먼저 1을 뺀 경우와 2로 나눈경우를 비교해서 작을 때에만 if문 안으로 들어간다.
    if i%2 == 0 and dp[i] > dp[i//2]+1 :
        dp[i] = dp[i//2]+1
    #3으로 나누어지면서, 먼저 1을 뺀 경우와 3으로 나눈 경우를 비교해서 작을 때에만 if문 안으로 들어간다.
    if i%3 == 0 and dp[i] > dp[i//3]+1:
        dp[i] = dp[i//3]+1
print(dp[n])

▲개선 답안 설명

dp테이블을 미리 생성하여 0으로 초기화하고 값을 대입하는 식으로 구현하였다. 

min을 사용하지 않고 if문에서 dp[i]와 dp[i//2]+1, dp[i//3]+1을 비교해서 걸러지도록 구현하였다.