boj 1463 : 1로 만들기

문제 주소: https://www.acmicpc.net/problem/1463

난이도: silver 3

1.문제설명

• 정수 X에 다음과 같은 연산을 할 수 있다.
• X가 3으로 나눠 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면 2로 나눈다.
• 정수 N이 주어졌을 때 위의 연산 3개를 적절히 사용해서 1을 만들려한다.
• 이때 연산을 사용하는 횟수의 최소값은?

2.문제해결 아이디어.

• DP테이블을 만든다.
• 최적화 하고싶은 것은 연산을 사용하는 횟수이다.
• minimize problem

3.문제접근법

• DP테이블을 초기화한다.
• 인덱스를 직관적으로 사용하기위해 0번째 인덱스는 만들고 사용하지 않는다.
• N이 1,2,3중에 하나라면 테이블에서 바로 출력하고 종료한다.
• 3보다 크다면 조건에 따라 아래 점화식을 점화시킨다.

'''2로도 나눠지고 3으로도 나누어 떨어지지 않는 경우'''
cache[i] = min(cache[i-1], cache[i//3], cache[i//2]) + 1
'''2로만 나눠지고 3으로는 나누어 떨어지지 않는 경우'''
cache[i] = min(cache[i-1], cache[i//2]) + 1
'''3으로만 나눠지고 2로는 나누어 떨어지지 않는 경우'''
cache[i] = min(cache[i-1], cache[i//3]) + 1
'''그 외'''
cache[i] = cache[i-1] + 1

4.특별히 참고할 사항

점화식을 점화시키기 전에 입력이 초기화된 값으로 답변될수 있을 경우와 아닌 경우를 나눠야함.

5.코드구현

n = int(input())
cache = [1e9] * (n+1)
cache[1] = 0 #1일 때
if n > 1:
    cache[2] = 1 #2일 때
if n > 2:
    cache[3] = 1 #3일 때

if n in [1,2,3]:
    print(cache[n])
    exit(0)
else:
    for i in range(4,n+1):
        if i%3 == 0 and i%2 == 0:
            cache[i] = min(cache[i-1], cache[i//3], cache[i//2]) + 1
        elif i%2 == 0 and i%3 != 0:
            cache[i] = min(cache[i-1], cache[i//2]) + 1
        elif i%2 != 0 and i%3 == 0:
            cache[i] = min(cache[i-1], cache[i//3]) + 1
        else:
            cache[i] = cache[i-1] + 1

print(cache[n])