[프로그래머스] 숫자 변환하기 (Level 2)

Problems

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

Idea

일단은, 수학적으로 일반해를 구하는 것은 좋지 않습니다. 사실 언제 더해주는 것이 좋을지 모르니까요.

다만 중요한 아이디어는, 값은 무조건 단조적으로 strictly하게 증가한다 입니다.

따라서, 이미 목표값을 넘는 것에 대해서는 더 연산을 시도해볼 이유가 전혀 없습니다.
이에 따라, 특정 수에 n을 더하거나, 2배, 3배 했을 때 목표값인 y 이하인 값들만 담아주면 됩니다.
즉, 이것을 실패한다는 것은, 단조성에 의거하여 불가능임이 확정됩니다. -1을 주고 break 시키면 됩니다.

실제 구현에서는 step별로 검토할 숫자의 목록들을 새로 초기화해서 담아주는 방식으로 짜면 매우 깔끔합니다.

Code

def solution(x, y, n):
    num_list = [x]
    count = 0
    
    while y not in num_list:
        new_num_list = []
        for cur_n in num_list:
            if cur_n + n <= y:
                new_num_list.append(cur_n + n)
            if cur_n * 2 <= y:
                new_num_list.append(cur_n * 2)
            if cur_n * 3 <= y:
                new_num_list.append(cur_n * 3)
        count += 1
        num_list = new_num_list
        # 중복된 값이 나올 수 있어, 연산량을 감소시킬 겸 줄여야 한다.
        # 중복값을 없애지 않으면 그 개수만큼 계속 지수 폭발로 연산량이 증가한다.
        num_list = list(set(num_list))
        
        if len(num_list) == 0:
            count = -1
            break          
            
    return count