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

문제 설명

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

x, y, n이 주어졌을 때
x에 x+n, x*2, x*3 의 연산을 수행해 y를 만들 수 있는 최소 연산값을 return하는 문제이다.
y를 만들 수 없다면 -1을 return한다.

 

처음에 제출한 코드(DP)와 틀린 이유

dp 배열의 가장 처음값을 -1로 설정하였고,
해당 숫자까지의 누적 연산 횟수를 저장시켰다.

def solution(x, y, n):
    dp=[-1]*(y + 1)
    dp[x]=0  # 연산 시작 
    
    
    for i in range(x,y):
    	# i에 누적 연산 횟수가 없다면 continue 
        if dp[i]==-1:
            continue
        
        # 누적 연산 횟수 갱신 
        for near in [i+n,i*2,i*3]:
            # near을 지나친 적이 없다면 i의 연산 횟수+1 저장 
            if near<=y and dp[near]==-1:
                dp[near]=dp[i]+1
    
    # x와 y의 값이 같다면 최소 연산 수는 0 
    if x==y:
        dp[y]=0
        
    answer=dp[y]
    
    return answer

 

제출했을 때 테케가 75%만 성공이었는데, 아무리 생각해봐도 틀린 이유를 찾을 수 없었다.
결국 다른 블로그를 참고해보니, dp[near] != -1 일 때 dp값의 대소비교를 해주지 않아서 틀린 것을 알 수 있었다.

dp[near] 값이 -1에서 다른 값으로 갱신이 되면 그 값이 최소가 된다고 생각하여 따로 대소비교를 해주지 않았다.

 

하지만 이 풀이 방식은 가지치기를 할 때 가능한 풀이였다. 처음에는 이 문제를 bfs로 접근해서 풀이에 혼동이 왔던 것 같다.... 난 바보다

가지치기를 하게 되면, 첫번째 연산으로 새로운 숫자들이 생기고 그 값들의 dp값은 1이다.
이와 같이 두번째 연산으로 새롭게 생기는 숫자들의 dp값은 2이다.
이렇게 따로 대소비교를 통해 값을 갱신해줄 필요가 없다.

 

제출한 코드에서는 for문에서 i를 순차적으로 증가시키면서 dp의 연산횟수를 찾는 것이기 때문에 연산횟수가 증가하는 순서대로 숫자들을 탐색하지 않게 된다. 따라서 갱신값과 기존 dp값의 대소비교가 필요하다.

 

수정한 코드(DP)

def solution(x, y, n):
    dp=[-1]*1000001
    dp[x]=0  # 연산 시작 
    
    # x와 y의 값이 같다면 최소 연산 수는 0 
    if x==y:
        return 0
    
    for i in range(x,y):
    	# i에 누적 연산 횟수가 없다면 continue 
        if dp[i]==-1:
            continue
        
        # 누적 연산 횟수 갱신 
        for near in [i+n,i*2,i*3]:
            if near<=y:
                if dp[near]==-1:    # near을 지나친 적이 없다면 i의 연산 횟수+1 저장 
                    dp[near]=dp[i]+1
                else:    # near을 지나친 적이 있다면 기존값과 비교 
                    dp[near]=min(dp[near],dp[i]+1)
                
    answer=dp[y]
    
    return answer

 

BFS 풀이

위에서 언급한 가지치기 방식으로 방문한 적이 없고 y보다 같거나 작은 숫자라면 방문하여 queue에 저장해서 y까지의 최소 연산 횟수를 구한다.
가장 처음 BFS로 풀려고 했을 때, visited를 설정해주지 않아서 시간초과가 떴었다.

from collections import deque

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

 

다른 풀이

n번째 연산결과를 set로 저장해주고, 카운트를 해주면서 y값이 해당 set에 있다면 cnt를 반환하는 풀이도 있다.

회고

정말 어렵지 않은 문제임에도 불구하고, 틀린 이유를 찾는게 너무 어려웠다.
처음 접근을 이상하게 하면 무한 굴레에 빠지게 되는 것 같다.