[Programmers | Level 2] 숫자 변환하기

IBLOG·2023년 5월 24일
0

programmers

목록 보기
24/26

programmers


문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

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

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.


제한사항

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

입출력 예

xynresult
104052
1040301
254-1

입출력 예 설명

입출력 예 #1

x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2

x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3

x를 y로 변환할 수 없기 때문에 -1을 return합니다.



Solution Code

Solution 1.

def solution(x, y, n):
    answer = 0
    s = set()
    s.add(x)
    
    while s:
        if y in s:
            return answer
        else:
            x = set()
            for i in s:
                if i+n <= y:
                    x.add(i+n)
                if i*2 <= y:
                    x.add(i*2)
                if i*3 <= y:
                    x.add(i*3)
            s = x
            answer += 1
            
    return -1

Solution 2.

from collections import deque

def solution(x, y, n):
    visited = [0] * 1000001

    q = deque()
    q.append((x, 0))
    visited[x] = 1
    while q:
        num, cnt = q.popleft()
        if num == y:
            return cnt
        for next_num in (num + n, num * 2, num * 3):
            if next_num <= y and not visited[next_num]:
                visited[next_num] = 1
                q.append((next_num, cnt + 1))

    return -1
profile
✢ 천천히 하나씩 기록해보자!

0개의 댓글