Programmers / 숫자 변환하기 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 숫자 변환하기 (2단계) - dp, bfs

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

---

일단 dfs로 접근하면 시간초과가 난다.

그리고 내 코드의 bfs로 접근시도 시간초과가 났다(왜지!)

 

그래서 최종적으로 dp로 접근하였다.

 

나의 풀이 - bfs

def solution(x,y,n):
    answer = -1
    if x == y:
        return 0
    queue = [(x+n,1),(x*2,1),(x*3,1)]

    visitied = []
    while queue:
        node = queue.pop(0)
        if node[0] == y:
            answer = node[1]
            break
        elif node[0] > y:
            pass
        else:
            tmp = []
            if node[0] + n <= y:
                tmp.append((node[0] + n,node[1]+1))
            if node[0] * 2 <= y:
                tmp.append((node[0] * 2,node[1]+1))
            if node[0] * 3 <= y:
                tmp.append((node[0] * 3,node[1]+1))          
            if tmp:
                queue.extend(tmp)

    return answer

 

나의 풀이 - dp

dp 는 알고리즘이 그렇듯이.. 일단 x부터 시작해야한다

dp[x] 는 가지가 0이다. (즉, 리스트 안의 값이 가지임)

초기 dp 상태는 가지가 1000001 이라고 해둔다. (최솟값을 찾아가는 과정이기 때문에 최댓값으로 설정)

그러므로 i + n번째,i*2 번째, i*3 번째의 가지값과 i번째에 있는 가지값을 비교한다.

dp[i]+1 과 비교하는 이유는 해당   i + n번째,i*2 번째, i*3 번째의 가지값이 최솟값이 아니라면 새로운 가지를 뻗어나가야한다는 이야기이다.

 

여기서 내가 계속 언급하는 가지는 사용하는 연산의 수이다.

 

def solution(x, y, n):
    dp = [1000001 for _ in range(y+1)]
    dp[x] = 0
    if x == y:
        return 0
    
    for i in range(x,y+1):
        if i + n <= y:
            dp[i+n] = min(dp[i+n],dp[i]+1)
        if i * 2 <= y:
            dp[i*2] = min(dp[i*2],dp[i]+1)
        if i * 3 <= y:
            dp[i*3] = min(dp[i*3],dp[i]+1)
    if dp[y] == 1000001:
        return -1
    return dp[y]

---

※ 알아야 할 것

- dp적 사고를 가지자... 항상 최댓값을 넣은 뒤 최솟값을 찾아가는 방법 모색

- dp[y]를 통해 해당 값이 1000001이면 최솟값을 구하지 못한것이므로 -1을 출력