프로그래머스_숫자 변환하기_Day3

 

알고리즘 풀이 챌린지 3일차이다. 평일에는 출근해서 점심시간에 짬짬이 풀고 포스팅을 하고 있지만,, 내일부터 시작될 설 연휴동안 문제를 풀 수 있을까 걱정이다.. ㅋㅋ 이왕 시작한거 연휴에도 쉬지 않고 매일 한 문제씩 꼭 진행해보자.

오늘은 프로그래머스 level2로 분류된 동적 계획법 문제를 가지고 왔다. 

https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=python3

프로그래머스

 

주어진 동전으로 내야하는 금액을 맞추는 것과 아주 비슷한 유형으로 크게 어렵지 않은 쉬운 DP 문제에 해당한다. 

문제에서 주어진 연산 또한 +n, *2, *3으로 정해져 있기 때문에 DP의 점화식이 뻔히 보이지 않는가? 

먼저 크기가 y+1인 DP 배열을 생성해주자. 
이떼, dp[i]는 x를 주어진 연산을 사용하여 i를 만들고자 할 때 필요한 최소 연산의 수이다.

점화식을 도출하기 위한 기본 공식은 아래와 같다. 

1. 인덱스 x부터 시작하면서 dp[x] 배열을 채워보자. 
2. x에 주어진 연산을 행한 결과 인덱스를 탐색해보자. 예시로 +n을 보자. 연산결과는 당연히 y보다 작거나 같아야 한다.
   1. 연산 결과 dp[x+n]이 0이라면, 아직 탐색하지 않은 숫자(x+n)인 것이다.
      1. dp[x] + 1을 값으로 할당해주자. 
   2. 연산 결과dp[x+n]가 0이 아니라면, 다른 숫자로부터 탐색된 숫자(x+n)인 것이다.
      1. dp[x] + 1 과 dp[x+n] 둘 중 최솟값을 배열에 저장해준다. 

위의 논리대로 *2, *3연산도 동일하게 진행하면 된다. 

이렇게 진행하다 보면,
알고리즘의 흐름은 초깃값에서 3번의 연산을 진행하고 반복 인덱스가 증가한다. 
기준 숫자 x에서 연산한 값(x+n, x*2, x*3)을 제외하고는 값을 -1로 초기화 해준다. (주어진 연산으로 만들 수 없는 수다!)

계속 -1로 초기화하다가 dp[i]가 0이 아닌 인덱스(기준 숫자에서 연산으로 만들 수 있는 수)를 찾게 되면, 위의 논리대로 연산을 진행한다. 

이렇게 진행하다보면 dp[y]값이 -1 혹은 최소 연산수로 채워지게 되고, 이 값을 리턴하면 된다. 

글로만 읽다보니 이해가 어려울 것 같아서 로직의 흐름을 간단하게 그림으로 표현해보겠다. 

 

배열을 생성한 후 가장 초기 상태는 아래와 같을 것이다.

 

여기에서 첫번째 반복을 통해 연산을 진행하면 아래와 같이 배열이 바뀐다.

 

반복의 인덱스가 1증가하면 아래와 같이 배열이 바뀐다.
n=1이 아니라면 x+1은 연산으로 만들수 없는 수다. 

위처럼 배열을 Bottom-up 방식으로 채워나가다 보면 y까지 채워질것이다.

 

이제 소스 코드를 보면서 이해해보길 바란다. 

Java 

class Solution {
    
    public int solution(int x, int y, int n) {
        int [] dp = new int[y+1];    
        
        for(int i=x; i<=y; i++) {
            
            //가장 처음 초깃값 (i==x) 제외 dp 값이 0이라는 말은 x에서 연산으로 만들 수 없는 값이다. 
            if(i!=x && dp[i] == 0) {
                dp[i] = -1;
                continue;
            }
            
            if(i * 2 <= y) {
                //현재값 * 2를한 인덱스의 값이 0이라면 (=아직 만들어지지 않았다면) 현재 값에 연산횟수 +1을 하고, 이미 값이 있다면 대소 비교 진행
                dp[i*2] = dp[i*2] == 0 ? dp[i] + 1 : Math.min(dp[i*2], dp[i]+1); 
            }
            
            if(i * 3 <= y) {
                dp[i*3] = dp[i*3] == 0 ? dp[i] + 1 : Math.min(dp[i*3], dp[i]+1); 
            }
            
            if(i + n <= y) {
                
                dp[i+n] = dp[i+n] == 0 ? dp[i] + 1 : Math.min(dp[i+n], dp[i]+1); 
            }
        }
        
        
        return dp[y];
    }
}

 

Python 

def solution(x, y, n):
    answer = 0
    dp = [0 for _ in range(y+1)]

    for i in range(x, len(dp)):
        if i != x and dp[i] == 0:
            dp[i] = -1
            continue
        
        if i + n <= y :
            dp[i+n] = dp[i] + 1 if dp[i+n] == 0 else min([dp[i]+1, dp[i+n]])
        
        if i * 2 <= y :
            dp[i*2] = dp[i] + 1 if dp[i*2] == 0 else min([dp[i]+1, dp[i*2]])
            
        if i * 3 <= y :
            dp[i*3] = dp[i] + 1 if dp[i*3] == 0 else min([dp[i]+1, dp[i*3]])    
        
    return dp[y]