[DP] 프로그래머스 고득점킷 N으로 표현 - Python 파이썬

 

생각하기

N을 사용한 횟수에 따라 단계를 나눌 수 있다

N을 사용한 횟수에 따라 단계를 나누게 된다면 N을 구하기 위해서는 이전에 구했던 것들을 사용해야 한다.

예를 들어 N을 3번 사용했다면 N을 1번 사용한 경우의 수와 N을 2번 사용한 경우의 수를 합치면 된다

따라서 이 문제는 DP를 통해 풀어보는 것으로 한다

 

구체화하기

dp[i] 는 N을 i번 사용했을 때 만들 수 있는 수의 집합 

ex ) N= 3일 때, dp[1] = { 3 } dp[2] = {33, 6, 0, 9, 1}

따라서 dp[i]를 만들기 위해서는 이전까지의 모든 결과들을 조합하여 dp[i]를 만들어야 함

 

dp[k] = dp[i] 사칙연산 dp[k-i] (i=1 ~ k-1) 

이런식으로 점화식 구성이 가능하지 않을까 싶다

 

1. 33, 333 같은 숫자들은 사칙연산으로 만들 수 있는 아이들이 아니다! 사전에 Dp 안에 넣어놓는다

2. 굳이 1부터 K-1까지 다 돌 필요는 없을 것 같다. 반만 돌고 나누기나 빼기 같은 것들은 한번에 처리하자

3. N을 1번 사용 했을 경우를 생각해서 예외처리 하자

 

def solution(N, number):
    # N을 i번 사용해서 만들 수 있는 수들의 집합 dp[1] = {5}, dp[2] = {55, 5+5=10, 5/5=1, 5*5=25, 5-5=0} 
    # dp[i]를 만들기 위해서는 dp[1] ~ dp[i-1]까지 1을 i-1에 사칙연산, 2를 i-2에 사칙연산
    if N == number:
        return 1
    
    
    dp = [set([0])]

    for i in range(1, 10):
        dp.append(set([(int)((str)(N)*i)]))
    
    for cur in range(2, 9):
        for i in range(1, cur//2+1):
            for num1 in dp[i]:
                for num2 in dp[cur-i]:
                    dp[cur].add(num1+num2)
                    dp[cur].add(num1-num2)
                    dp[cur].add(num2-num1)
                    dp[cur].add(num1*num2)
                    if num2 != 0:
                        dp[cur].add(num1//num2)
                    if num1 != 0:
                        dp[cur].add(num2//num1)
        if number in dp[cur]:
            return cur
        
    answer = -1
    return answer