사용자 도구

사이트 도구


ps:problems:programmers:42895

N으로 표현

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42895
출처프로그래머스
문제 번호42895
문제명N으로 표현
레벨Level 3
분류

DP

시간복잡도O(n^2*m*10^m)
인풋사이즈n<=9, m<=8
사용한 언어Python
해결날짜2020/11/30

풀이

  • 0에서부터 시작해서 k를 증가시켜가면서 N을 k번 사용해서 만들 수 있는 모든 수를 만들어보고 그 중에 number가 있는지 확인해본다.
  • N을 k번 사용해서 만들 수 있는 모든 수를 찾는 것은 DP를 이용한다
  • dp[k] 를 N을 k번 사용해서 만들 수 있는 수의 집합이라고 하면
    • $ dp[i] = \bigcup_{j=1}^i \bigcup_{a\in dp[j]} \bigcup_{b\in dp[i-j]}\left\{a+b, a-b, a \times b, a \div b \right\} $ 으로 점화식을 세워진다.
  • 시간복잡도를 구해 보려했으나 만만치 않다..
    • 각 dp[i]의 크기 |dp[i]| = O(sigma( 4 * |dp[j]| * |dp[i - j]| ) + 1) 으로 카탈랑 수 (Catalan number)에 4^i를 곱한 형태로 나온다. 즉, O(4^(2i) / i^(3/2)). 이 크기는 dp[i]를 만들기 위한 연산 횟수와 동일하니까, 전체 연산 수는 O(|dp[1]| + |dp[2]| + … + |dp[m]|) 인데… 이거는 너무 범위가 크다; 다른 방법을 생각하자
    • 각 dp[i]의 크기의 바운드를 N을 i번 써서 만들수 있는 최소값과 최대값으로 생각하자..
      • N을 i번 써서 만들수 있는 최대값은 그냥 N을 i번 붙여쓴 NNN….N이다. 최대값=N*(10^i-1)/9 이고 최소값도 -만 붙이면 되니까 |dp[i]| = O(N*10^i).
      • dp[i]를 계산할 때는 O(sigma( 4 * |dp[j]| * |dp[i - j]| ) + 1) 의 연산이 필요한건 동일하다. O(i*4*N^2*10^i)
      • 이 값을 i≤m 까지 모두 더한 합은 대충 O(N^2*m*10^m)
      • 16^m 이 포함되어있던 위의 식보다는 좀더 타이트해지긴 했지만.. 만족스럽지는 못하다. 그러나 이게 나의 한계인듯 ㅜ
  • 이렇게 bottom-up으로 dp를 만들지 않고서 top-down으로 number에서부터 시작해서 만들어가려 하는 것은 “나누기 연산에서 나머지는 무시합니다.” 라는 조건때문에, 좀 힘들다. f(x) = min(f(x+N), f(x-N), f(x/N), f(x*N), f(x*N+1), f(x*N+2), …)+1 이런식이 되기 때문이다.

코드

"""Solution code for "Programmers 42895. N으로 표현".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42895
- Solution link: http://www.teferi.net/ps/problems/programmers/42895
"""

MAX = 8


def solution(N, number):
    dp = [set() for _ in range(MAX + 1)]
    dp[0] = {0}
    for i in range(1, MAX + 1):
        dp[i] = {int(str(N) * i)}
        for j in range(1, i):
            for n1 in dp[j]:
                for n2 in dp[i - j]:
                    dp[i] |= {n1 + n2, n1 - n2, n1 * n2}
                    if n2 != 0:
                        dp[i].add(n1 // n2)
        if number in dp[i]:
            return i        
    return -1

토론

댓글을 입력하세요:
R N U᠎ R N
 
ps/problems/programmers/42895.txt · 마지막으로 수정됨: 2021/05/26 15:32 저자 teferi