🐹 N으로 표현

1. 문제 링크

N으로 표현

2. 코드

def solution(N, number):
    # 이어 붙인 숫자 초기화 
    dp = [set([int(str(N)*i)]) for i in range(1, 9)]
    
    # N 사용 횟수
    for cnt in range(8):
        for i in range(cnt):
            # N의 총 카운트 개수 중 i개
            for num1 in dp[i]:
                # N의 총 카운트 개수 중 i개를 제외한 나머지
                for num2 in dp[cnt-i-1]:
                    dp[cnt].add(num1 + num2)
                    dp[cnt].add(num1 - num2)
                    dp[cnt].add(num1 * num2)
                    if num2 != 0:
                        dp[cnt].add(num1 // num2)
        # number가 연산 결과에 있으면 리턴
        if number in dp[cnt]:
            return cnt + 1
        
    return -1

• 정확성

  테스트 1 〉	통과 (0.86ms, 10.4MB)
  테스트 2 〉	통과 (0.03ms, 10.4MB)
  테스트 3 〉	통과 (0.06ms, 10.1MB)
  테스트 4 〉	통과 (27.03ms, 11.1MB)
  테스트 5 〉	통과 (13.39ms, 10.9MB)
  테스트 6 〉	통과 (0.21ms, 10.3MB)
  테스트 7 〉	통과 (0.20ms, 10.4MB)
  테스트 8 〉	통과 (20.73ms, 11.3MB)
  테스트 9 〉	통과 (0.03ms, 10.2MB)

3. 해설

N을 사용한 수가 최소가 되도록 하여 값을 구하기 위해 N을 1개부터 8개까지 차례대로 사용해보며 그 중 number가 있을 시의 N의 사용 개수를 리턴해준다.

N을 1개 사용했을 때 나올 수 있는 경우 → N (한 개)

N을 2개 사용했을 때 나올 수 있는 경우 → NN, N + N, N - N, N * N, N / N (다섯 개)

차례대로 나열하다보면 N을 8개 사용했을 경우는 NNNNNNNN을 나열한 경우를 제외하고는

(N을 i개 사용했을 때 결과 값들)과 (N을 8-i개 사용했을 때 결과 값들) 이 두 가지 케이스를 연산한 경우가 8개를 사용하여 계산한 케이스들의 결과값이다.

따라서 dp를 N을 나열한 경우로 초기화 해준 후, 1부터 8까지 순서대로 사용하여 연산 결과에 넣어준다.

이때 연산 결과값들 중 number가 있다면(가장 먼저 발견) 사용한 N의 개수를 리턴해준다.

만약 8번까지 계산 중에서도 number가 나오지 않는다면 -1을 리턴해준다.