백준 1463번 - 1로 만들기

 

숫자마다 최소 시행 횟수를 계산하다보면, i의 최솟값은 i가 3으로 나누어 떨어진다면, i//3의 최소 시행 횟수와 연관이 있고 2로 나누어 떨어진다면 i//2와, 둘다 나누어 떨어지지 않는다면, i-1과 연관이 있다는 사실을 알 수 있다.

그럼 우리가 비교해야 할 값들은 numbers[i-1]과 numbers[i//2]+1과 numbers[i//3]+1이다. 

조심해야 할 점은 if ~ elif ~else로 쓰지말고 if~if로 써서 2와 3으로 모두 나누어 떨어지는 경우도 생각해줘야한다.

 

##변수 선언 부분##
numbers = []

##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    numbers = [-1,0] #N=0, N=1일때 최솟값
    for i in range(2,N+1):
        numbers.append(numbers[i-1]+1) #이전 값에 1을 더한 횟수를 일단 넣어준다.
        if i % 3 == 0: #3으로 나누어 떨어지면,
            numbers[i] = min(numbers[i], numbers[i//3]+1) #이전 값의 정답에 1을 더한 값과 비교
        if i % 2 == 0:
            numbers[i] = min(numbers[i], numbers[i//2]+1)

    print(numbers.pop())

DP문제는 대부분 이전 시행들과 밀접한 관련이 있음을 깨달았다. 문제가 안풀린다면 이전 시행들과 현재 시행의 연관성에 대해 생각하면서 다시 풀어보자