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

 

 

문제 링크

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

프로그래머스

 

 

 

TIL

• 경우의 수가 너무 많아서 시간복잡도 및 공간복잡도가 좋지 않을 것으로 생각했지만, DP의 경우 어쩔 수 없는 느낌
  • O(n^2)까지는 그냥 가자
• 문제에서 8이상이면 모두 -1 처리를 하라고 했기 때문에 복잡도를 생각하지 않아도 됐음
• 이런 식으로 피보나치 느낌의 문제들은 DP 먼저 생각하기 !!

 

# dp-tabulation 

def solution(N, number):
    tabu = [-1 for i in range(number)]
    
    for i in range(1, number+1):
        cmt = 0
        temp = 0
        if i < N:
            while temp < i:
                cnt += 2
                temp += 1
        elif i == N:
            cnt += 1
        else:
            
        if cnt > 8:
            break
        tabu[i] = cnt

 

• 처음에 생각한 방법이 힘들다 생각한 이유
  • number를 기준으로 tabu를 구하려고 했음
  • 1인 경우, 2개 이런 식으로
  • 만약에 9인 경우, 1+8인 최소인지, 2+7이 최소인지 등 찾기가 힘들어짐 >> 완전 탐색해야함
  • 근데 이것도 되네 결국 아래 방법도 완전탐색함
  • 대신 아래 방법은 for 문을 8까지만 확실하게 돌릴 수 있음. >> 이걸 기준으로 생각해야될듯 앞으로도 !!
• 반대로 생각하는 방법! >> 풀이 외우기
  • 1개를 사용할 때, 가능한 숫자의 경우를 저장하자
  • dp[1] = [5], dp[2] = [1, 55, 25, 6, 10, 0] ... 이런식으로 될 수 있음 
  • for 문으로 주어진 숫자가 dp 안에 있나 확인하면 됨
    • if number in dp[i] >> 이러면 가장 최소부터 찾게됨 (for문이 작은 수부터 시작하니까)
• 간단한 팁
  • 숫자를 그냥 이어붙이려면 str로 변경 후 곱하기. 이후 다시 int로 변경
• 중복을 골라내기 위해 set() 사용하자 !!
  • dp = [] > 이렇게 하면 중복을 골라낼 수 없음
  • dp[i]는 N을 i번 사용해서 만들 수 있는 수의 집합 >> dp = [set() for _ in range(9)]
• 합해서 뭐가 되는 것을 구할 때
  • 구해야하는 합이 s라면 i 두고, 한 개는 i / 다른 거는 s-i 와 같은 방식으로 변수 설정 > 합해서 s !

 

 

Code

# dp-tabulation 

def solution(N, number):
    
    if N == number:
        return 1

    # dp = [] > 이렇게 하면 중복을 골라낼 수 없음
    # dp[i]는 N을 i번 사용해서 만들 수 있는 수의 집합
    dp = [set() for _ in range(9)]
    
    for i in range(1,9):
        dp[i].add(int(str(N)*i))
        
        for j in range(1,i):
            for x in dp[j]:
                for y in dp[i-j]:
                    dp[i].add(x+y)
                    dp[i].add(x-y)
                    dp[i].add(x*y)
                    if y!=0:
                        dp[i].add(x//y)
        
        if number in dp[i]:
            return i
    return -1