N으로 표현

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

프로그래머스

 

I. 문제 개요

검증해야 하는 경우의 수가 과도하기에, 단순히 모든 경우의 수를 다 탐색하기에는 무리가 따른다.

DP(Dynamic Programming)를 활용하여 살펴본 경우의 수를 저장하면, 모든 경우를 일일히 계산하는 수고를 덜 수 있다.

 

II. 알고리즘 설계 및 풀이

1. 변수 초기화

ans = -1
dp = [set() for _ in range(9)]

dp는 N을 사용한 횟수별로 나울 수 있는 수들을 저장한다.

dp[1]은 N을 1번, dp[5]는 N을 5번 사용하는 경우에 나올 수 있는 모든 수들을 저장한다.

set을 활용하여, 계산 결과를 탐색할 때의 시간복잡도를 O(1)으로 단축할 수 있다.

 

2. DP 활용

for i in range(1, 9):
    case = dp[i]                  # i개의 N을 사용하여 만들 수 있는 숫자들
    case.add(int(str(N) * i))     # N을 i회 사용한 숫자 넣기

    for j in range(1, i):         # j:   N을 몇 번(1회 이상, i-1회 이하) 사용할 지
        for k in dp[j]:           # k:   j개의 N으로 만들 수 있는 수들
            for l in dp[i-j]:     # l:   이전에 파악한 수들 (j-1개의 N으로 만들 수 있는 수, ... , 1개의 N으로 만들 수 있는 수 )
                case.add(k + l)
                case.add(k - l)
                case.add(k * l)
                if k * l != 0 :   # k, l이 둘 다 0이 아니면
                    case.add(k // l)

    if number in case:
        ans = i
        break

return ans

case는 N을 i회 사용하여 만들 수 있는 수들을 담는 set() 이다.

우선, N을 i회 사용하여 만들 수 있는 수를 `case`에 저장한다.

N을 j개 사용하여 만들 수 있는 수들(k)과, N을 i-j개 사용하여 만들 수 있는 수들(l)을 조합하면, N을 i회만큼 사용하여 만들 수들의 조합을 구할 수 있다.

가능한 모든 수들을 계산하여, case에 집어넣는다.

만약 조합에 집어넣은 수 사이에 원하는 숫자 number가 들어있다면, 답안 ans의 값을 i로 바꾸고 for-loop을 탈출한다.

 

III. 전체 코드

def solution(N, number):
    # 1. 변수 초기화
    ans = -1
    dp = [set() for _ in range(9)]

    # 2. DP 활용
    for i in range(1, 9):
        case = dp[i]
        case.add(int(str(N) * i))

        for j in range(1, i):         # j:   N을 몇번 사용할 지
            for k in dp[j]:           # k:   j개의 N으로 만들 수 있는 수들
                for l in dp[i-j]:     # l:   이전에 파악한 수들 (j-1개의 N으로 만들 수 있는 수, ... , 1개의 N으로 만들 수 있는 수 )
                    case.add(k + l)
                    case.add(k - l)
                    case.add(k * l)
                    if k * l != 0 :   # k, l이 둘 다 0이 아니면
                        case.add(k // l)

        if number in case:
            ans = i
            break

    return ans

 

IV. 제출 결과