1463. [Python]1로 만들기

1. 문제

 

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

1463번: 1로 만들기

 

2. 접근 방법

 

• 시간 제한: 0.15초 (python 3 => 1.5초)
• 메모리 제한: 128MB
• DP(Dynamic Programming)

 

3. 파이썬 코드

 

def answer(num):
    # 0, 1 인 경우는 count 되는 값이 없어서 0
    # 2, 3 인 경우는 한번씩 나누는 값 1이다.
    # 외의 10^6 까지 값이 존재하므로 10^6+1 갯수 리스트 생성
    num_list = [0,0,1,1] + [0]*(10**6-2)
    # 4부터 시작하는 반복문 생셩
    for i in range(4, 10**6+1):
        # 6의 배수인 경우 2로 나눈 값과 3으로 나눴을 때 값을 비교해서 작은 값을 넣어준다.
        if i % 3 == 0 and i % 2 == 0:
            num_list[i] = min(num_list[i // 3]+1,num_list[i // 2]+1)
        # 그 외의 경우
        else:
            # 3으로 나눠지면 i//3 의 인덱스 값을 가져와서 + 1 한 값과 바로 직전의 값에서 + 1 해준 값의 대소를 비교
            if i % 3 == 0:
                num_list[i] = min(num_list[i // 3]+1,num_list[i-1] + 1)
            # 2으로 나눠지면 i//2 의 인덱스 값을 가져와서 + 1 한 값과 바로 직전의 값에서 + 1 해준 값의 대소를 비교
            elif i % 2 == 0:
                num_list[i] = min(num_list[i // 2]+1,num_list[i-1] + 1)
            # 그 외의 경우는 -1 되는 경우밖에 없기 떄문에 직전의 값에서 +1 을 해준다.
            else:
                num_list[i] = (num_list[i-1] + 1)
    return num_list[num]
N = int(input())

print(answer(N))

 

4. 문제를 풀고난 후 생각

 

• DP(Dynamic Programming)의 문제로 이전의 값들에서 쌓아 올라가는 bottom-up 구조로 푸는 문제다.
• 알고리즘을 푸는데 있어서 DP 문제는 무조건 적으로 알아둬야 하는 개념으로 중요하다.
• 이 문제는 주어진 숫자로부터 구하는 것이 아닌 값들을 미리 구해두고 난 후 그 숫자를 넣어서 값을 도출해내는 방식으로 풀었다.
• 숫자가 10^6 까지만 들어오기 때문에 리스트를 10^6 + 1 개 생성을 한 후 전의 값들을 사용해가며 값을 구해준다.
• index 1, 2, 3 에 들어있는 값들이 index의 count 값들이 되고, 4부터는 2로 나눴을 때 0이 되는 경우, 3으로 나눴을 때 0이 되는 경우 각각 나눠서 생각을 하고 나누어 떨어진 다면 i 값을 2,3 으로 나눈 몫의 인덱스 값을 가져와서 + 1 을해주면 그 index 값에는 숫자를 넣었을 때 몇번 연산되는지 갯수가 된다.
• 특이한 경우는 6으로 나눠 떨어지면 2, 3 둘다 적용되기 때문에 이때는 2로 나눈 값과 3으로 나눈 값 중 작은 값을 선택해서 넣어줘야한다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(Dynamic Programming)