[DP] N으로 표현 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

이러한 DP 문제에서 경우의 수를 다루는 문제를 익혀야 한다...!

 

여기서도

5를 1번만 쓴 경우 만드는 경우의 수

[5]

5를 2번 쓴 경우 만드는 경우의 수

[55, (5+5), (5-5), (5/5), (5*5)]

이렇게 경우의 수를 생각해볼때

 

5를 3번 쓴 경우를 만드는 경우의 수는 다음과 같다

555를 먼저 추가해주고

[5] 와 [55, (5+5), (5-5), (5/5), (5*5)] 사이의 사칙연산 (+, -, /, *)

[55, (5+5), (5-5), (5/5), (5*5)] 와 [5] 사이의 사칙연산 (+, -, /, *)

이 렇게 부분적으로 문제를 풀 수 있다

즉 1번 경우의 수 X 2번 경우의 수 and 2번 경우의 수 X 1번 경우의 수 이다

여기서 이런 아이디어를 발견할 수 있냐는 거다

 

5를 4번 쓴 경우는 어떠할까

이는 다음과 같이 나타낼 수 있다

3번 경우의 수 X 1번 경우의 수

2번 경우의 수 X 2번 경우의 수

1번 경우의 수 X 3번 경우의 수

 

즉, 이러한 큰 문제를 작은 문제의 반복? 으로 나타낼 수 있다.

경우의 수 문제는

동전 문제도 그렇고

2원 짜리만 쓴 경우, 5원 짜리만 쓴 경우 ...

5를 1번 쓴 경우, 2번 쓴 경우 ...

 

작은 단위를 구하고

큰 단위를 추적하는 (점화식 마냥) 방법으로 이루어진다

 

import math
def solution(N, number): 
    if N == number : return 1
    dic = {}
    for i in range(1, 9) : 
        dic[i] = set()
    for i in range(1, 9) :
        if i == 1 : dic[i].add(N)
        if i >= 2 :
            if int(str(N)*i) == number : return i
            dic[i].add(int(str(N)*i))
            a = 1; b = i-1
            while a < i :
                for k in dic[a] :
                    for j in dic[b] :
                        if j+k == number : return i
                        if k != 0 :
                            if j // k == number : return i
                        if j - k == number : return i
                        if j * k == number : return i
                        dic[i].add(j+k)
                        if k != 0 :
                            dic[i].add(j//k)
                        dic[i].add(j-k)
                        dic[i].add(j*k)
                if a == b : pass
                for j in dic[a] : 
                    for k in dic[b] : 
                        if j + k == number : return i 
                        if k != 0 : 
                            if j // k == number : return i
                        if j - k == number : return i
                        if j * k == number : return i
                        dic[i].add(j + k)
                        if k != 0 : 
                            dic[i].add(j // k)
                        dic[i].add(j - k)
                        dic[i].add(j * k)
                a += 1
                b -= 1
            
    if number in dic[i] : return i
    else : return -1