[프로그래머스]N으로 표현 : 다이나믹 프로그래밍

jiseung·2021년 12월 26일
0

Algorithm

목록 보기
4/5

N으로 표현

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

숫자 N과 number가 주어질 때, N과 사칙연산, 괄호만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return하는 solution 함수 작성하기

Solution

dp[ [] ] : 8개의 일차원 배열로 이루어진 이차원 배열
dp[i] : N을 i개 사용해서 만들 수 있는 모든 숫자의 집합

  1. N을 문자처럼 연결해서 만들 수 있는 숫자로 이차원 배열을 초기화한다.
    5, 55, 555...
  2. for(i = N 1개 사용 ~ 8개 사용)에 대해서
    이미 계산된 값들을 이용해서 가능한 모든 경우의 수를 구한다.
    : 두 부분(사칙 연산의 왼쪽 값, 오른쪽 값)으로 쪼개서 가능한 모든 사칙연산 결과값을 추가한다.
// i는 이차원 배열 안을 순회하는 임의의 인덱스라고 가정한다.
// ?는 가능한 사칙연산이라고 가정한다. (+,-,*,/)

number가 2라면
dp = [[], [2], [22], [222] ...]와 같이 초기화한다.

dp[2]
dp[1]로 dp[2]를 구한다.
2+2 2-2 ...
(dp[1] ? dp[1])

dp[3]
dp[1]과 dp[2]로 dp[3]을 구한다.

2 ? (2 ? 2)
(dp[1][i] ? dp[2][i])

(2 ? 2) ? 2
(dp[2][i] ? dp[1][i])

dp[4]
(dp[1][i] ? dp[3][i])
(dp[2][i] ? dp[2][i])
(dp[3][i] ? dp[1][i]) // 빼기, 나누기 연산만 해도 된다

...
dp[k]
dp[1] ... dp[k-1]로 dp[k]를 구한다.
(dp[1~k-1][i] ? dp[k-1~k][i])
  1. 각 단계마다 number가 있는지 확인하고 찾으면 i를 반환한다.

코드

def solution(N, number):
    answer = -1
    # 중복된 값을 넣지 않기 위해 set() 사용
    dp = [set() for i in range(9)]
    dp[0].add(0)
    
    # N과 number가 같다면 한번에 해결
    if N == number:
        return 1
    
    # N을 연달아 붙여서 나타내는 경우 (ex) 5, 55, 555...)
    for i in range(1, 9):
        dp[i].add(int(str(N)*i))
    
    # 사용하는 N의 개수를 늘려가면서 순회한다
    for i in range(2, 9):
        # 사칙 연산의 왼쪽 부분과 오른쪽 부분으로 나눈다
        for j in range(1, i):
            # 왼쪽 부분이 될 수 있는 값
            for d1 in dp[j]:
                # 오른쪽 부분이 될 수 있는 값
                for d2 in dp[i-j]:
                    # 가능한 모든 사칙연산
                    dp[i].add(d1+d2)
                    dp[i].add(d1*d2)
                    dp[i].add(d1-d2)
                    if d2 != 0:
                        dp[i].add(d1//d2)
        # number를 찾으면 현재 i가 최소 개수!
        if number in dp[i]:
            return i
    
    return answer
profile
Frontend Web Developer

0개의 댓글