[4코1파] #77. LV 2. 숫자 변환하기

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (77일차)
[4코1파] 2023.01.13~ (68일차)

Today :

2023.03.20 [77일차]

프로그래머스 LV 2
숫자 변환하기
https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제 설명

자연수 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

입출력 예

입출력 예 설명

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

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

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

문제 풀이 방법

처음 시도는 연산자를 리스트에 넣고,
리스트를 돌면서 계산한 후에 임시 리스트에 넣고 체킹하는 로직이었는데
몇 테스트 케이스에서 실패했다.
이게 문제를 자세히 읽어보니까 여러 연산이 복합적으로 일어날 수 있는거라서
이렇게 풀면 안된다는 걸 알아차림..

머리는 돌아가지 않아서 구글링함.. 다른 새럼꺼 로직을 참고했다
로직보고 문제 이해한 나 레전드

내 코드

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

증빙

다른 사람 풀이

dp를 활용한 풀이

여담

생각보다 엄청 어려운 문제는 아니였는데 못 푼 나 레전드 ~
빠갈통