[프로그래머스]Lv2. 숫자 변환하기(Python)

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

프로그래머스

 

문제 접근

 

이전에 풀었던 문제인 백준의 '1로 만들기'와 비슷하다고 생각했다. 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

위의 문제를 풀 때 dp를 사용했던 기억이 있어서 이 문항도 dp를 사용하면 될 것이라고 생각했다.

 

추가고민(2/7)

우선 +n / *2 / *3 의 모든 경우가 가능하기 때문에  무한대로 초기화 있는 값을 만약 해당 경로가 가능하면 업데이트 해준다. 

 

코드

 

def solution(x, y, n):
    answer = 0

    dp = [1e9] * (y + 1)

    dp[x] = 0   # 시작점 x의 연산 횟수는 0

    # dp[i] = 자연수 i에 도달하기 위한 최소 연산 횟수
    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)

    # y 위치의 값이 초기값이라면, x=>y인 경로가 없다는 의미 
    if dp[y] == 1e9:
        return -1

    return dp[y]

 

문제 회고

 

처음 문제를 보고 dp라는 직감은 왔지만 dp 테이블을 무작정 0으로 초기화했다.

 

1. dp 테이블을 큰 수로 초기화한 경우:

아직 방문하지 않은 위치의 dp 값은 그대로 큰 수(-1 리턴), 도달하면 dp[y]로 갱신

 

2. dp를 0으로 초기화한 경우:

그냥 저 아래의 조건문을 dp[y] == 0 으로만 바꿔주면 되는거 아닌가? 라고 생각

하지만 dp[y] == 0인 상황은 두 가지!

(1) y 위치에 도달하지 못한 경우 

(2) y 위치에 도달하는 데 필요한 연산 횟수가 실제로 0인 경우 

=> 그렇기 때문에 dp테이블을 0으로 초기화하면 y 위치의 도달여부를 정확히 판단할 수 없다.