[프로그래머스 / Python] N으로 표현

문제 링크: programmers.co.kr/learn/courses/30/lessons/42895

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

 

 

문제 설명

처음엔 number에 대한 dp 테이블을 생성해서 문제를 풀려했는데, 그게 아니라 N의 사용 횟수에 대한 dp 테이블을 이용해 문제를 해결해야 했다. 문제에서 최솟값이 8보다 클 경우 -1을 반환한다고 나와있으므로 N을 8번 사용하는 경우까지만 계산하면 된다. 

 

N을 i번 사용하는 경우 만들 수 있는 수:

   - NNN...N (N이 i번 반복되는 경우)

   - (N을 1번 사용한 수) 사칙연산 (N을 i - 1번 사용한 수)

   - (N을 2번 사용한 수) 사칙연산 (N을 i - 2번 사용한 수)

   ...

   - (N을 i - 1번 사용한 수) 사칙연산 (N을 1번 사용한 수)

 

 

이처럼 N을 1번 사용하는 것부터 8번 사용하는 경우까지를 각 집합에 넣고, 만약 number가 해당 집합의 원소라면 i를 반환하면 된다. 

 

 

 

 

소스코드

from collections import defaultdict

def solution(N, number):
	# dp[i]: N을 i번 사용해서 만들 수 있는 수들의 집합
    dp = defaultdict(set)

    for i in range(1, 9):
        dp[i].add(int(str(N) * i))  # NNN...N
        for j in range(1, i):
            for n1 in dp[j]:
                for n2 in dp[i - j]:
                    dp[i].add(n1 + n2)
                    dp[i].add(n1 - n2)
                    dp[i].add(n1 * n2)
                    if n2 != 0: dp[i].add(n1 // n2)  # 0으로 나눌 수 없음

        if number in dp[i]: return i # N을 i번 사용해서 number를 만들 수 있음

    return -1 # 최솟값이 8번보다 클 경우