[프로그래머스] 숫자 변환하기

링크

문제 설명

입력으로 1 이상의 정수 x 와 y 가 주어진다. 주어진 아래 연산으로 x를 y로 만든다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

x를 y로 변환하는 최소 연산 횟수를 구한다. 변환할 수 없다면 -1을 반환한다.

제한사항

def solution(x: int, y: int, n: int) -> int:
        ...

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

풀이

DP를 응용해 풀었다. 크기가 y+1인 배열을 만들어 INF로 초기화한다. +1은 직관적으로 값과 인덱스를 일치시키기 위함이다. 각 배열의 원소는 해당 인덱스까지 연산을 수행한 횟수를 나타낸다.

문제 입력으로 주어진 x=10, n=5, y=40을 예시로하면 아래 그림과 같다. 시작점인 DP[x] 는 0으로 초기화한다.

이 DP 배열을 x 부터 y+1까지 순회하며 문제에 주어진 세가지 연산을 수행해 연산 결과값에 DP[i]+1을 해준다. 최소 횟수를 구하는 것이기 때문에 계산한 값과 배열에 저장된 값을 비교해서 더 작은값으로 바꿔야한다. 이를 빌트인함수인 min() 함수를 사용한다.

이를 계속 반복해서 수행하면 DP[y]에 y로 변환하기위한 최소 횟수가 저장된다. 이 값을 정답값으로 반환한다.

제출 코드

def solution(x: int, y: int, n: int) -> int:
    DP = [float('inf') for _ in range(y + 1)]
    DP[x] = 0

    for i in range(x, y + 1):
        if i * n <= y:
            DP[i] = min(DP[i + n], DP[i] + 1)
        if i * 2 <= y:
            DP[i] = min(DP[i * 2], DP[i] + 1)
        if i * 3 <= y:
            DP[i] = min(DP[i * 3], DP[i] + 1)

    return DP[y]