백준 22.02.10. 1463번 - 1로 만들기

N = int(input())

# dp의 범위가 0 ~ n까지 저장할 수 있도록 범위를 N+1까지 지정합니다.
dp = [0 for i in range(N+1)]


for n in range(2, N+1):

    # n에서 1을 뺀 후 dp[n-1]의 과정을 실행할 때의 값(해당 수의 연산 최댓값)
    dp[n] = dp[n-1] + 1

    # n을 3으로 나눌 수 있을 때
    if n % 3 == 0:
        dp[n] = min(dp[n], dp[n//3] + 1)

    # n을 2로 나눌 수 있을 때
    if n % 2 == 0:
        dp[n] = min(dp[n], dp[n//2] + 1)

# n의 연산 최솟값 출력
print(dp[N])

 

• 우선 입력받은 수까지 연산 최솟값을 저장할 dp리스트를 만듭니다
• dp리스트의 인덱스는 주어진 정수, 값은 그 정수를 연산하는 횟수의 최솟값을 저장할 것입니다.
  • ex) dp[2] = 1, dp[3] = 1, dp[4] = 2, dp[5] = 3, dp[6] = 2 ...
• 그리고 조금 더 직관적으로 알아보기 위해서 0인덱스는 활용하지 않을것입니다.
  • n은 1보다 크거나 같기 때문입니다.
• dp리스트의 길이는 n까지 저장하기 위해서 반복범위를 n+1까지 설정해줍니다.
• n번째 정수의 연산 최댓값은 n-1번째 정수에서 연산을 한 번 더한 것이므로 dp[n]을 최댓값으로 지정해줍니다.
  • dp[4] = 2이고 dp[5] = 3 일 때 dp[5]는 "5 - 1"의 연산을 실행한 후 dp[4]와 동일한 연산을 하기 때문입니다.
• 이어서 n이 3의 배수일 때와 2의 배수일 때 연산을 각각 if조건문으로 실행해줍니다.
  • if로 사용하는 이유는 3과 2 모두의 배수일 때도 (겹칠 때 ex. 6) 해당 연산을 통해서 2로 나누는 것이 연산 최솟값인지, 3으로 나누는 것이 연산 최솟값인지 모두 연산을 실행해보아야 하기 때문입니다.
• n이 3의 배수라면(3으로 나누어 나머지가 0이라면) n은 (n/3 * 3)이므로 dp[n]은 n/3의 연산 최솟값 + 1입니다.
  • => n을 3으로 나눈 뒤 dp[n/3]과 동일하기 때문입니다.
• n이 2의 배수라면 3의 배수일 경우와 동일하게 n은 (n/2 * 2)이므로 dp[n]은 n/3의 연산 최솟값 + 1입니다.
• 연산을 하며 갱신되는 dp와 조건에 맞게 새롭게 구해진 값을 비교하여 최솟값을 dp[n]에 저장합니다.