[프로그래머스 Lv.3] N으로 표현 (Python)

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

프로그래머스

풀이

number를 만들기 위해 필요한 N의 수를 구하는 문제이다. 하지만 문제의 조건을 살짝 다르게 생각하여 풀이하면 쉽게 해당 문제를 풀이할 수 있다.

N을 i개 사용해서 만들 수 있는 숫자들을 알아내고, 만약 원하는 숫자가 알아낸 숫자들 안에 있는지를 확인하면 된다. 또한 N을 i개 사용해서 만들 수 있는 숫자는 (N을 i-j개 사용하여 만들 수 있는 숫자)(사칙연산)(N을 j개를 사용해 만들 수 있는 숫자)임을 사용하면 DP로 문제를 풀 수 있다. (단, j는 0 < j < i인 정수)

 

예를 들어 2로 11를 만드는 경우를 생각해 보자. 앞서 말한 대로 조건을 살짝 다르게 생각해서 2를 i개 사용해서 만들 수 있는 숫자를 알아내면서 11가 나오는 경우를 알아내면 된다.

우선 2 하나로 만들 수 있는 숫자를 알아낸다. 이는 당연히 "2"이다.

이어서 2를 2개 사용해서 만들 수 있는 숫자를 알아낸다. 이는 2를 연속으로 2개 사용해서 만드는 숫자인 22 또는 (2를 1개 사용해서 만들 수 있는 숫자) (사칙연산) (2를 1개 사용해서 만들 수 있는 숫자)인 2 + 2 = 4, 2 - 2 = 0, 2 * 2 = 4, 2 // 2 = 1이다. 즉, "0", "1", "4", "22"이다.

다음으로 2를 3개 사용해서 만들 수 있는 숫자를 알아낸다. 이는 (2를 2개 사용해서 만들 수 있는 숫자) (사칙연산) (2를 1개 사용해서 만들 수 있는 숫자)와 (2를 1개 사용해서 만들 수 있는 숫자) (사칙연산) (2를 2개 사용해서 만들 수 있는 숫자)이다. 여기서 우리는 11을 만들 수 있는데 2를 2개 사용해서 만든 22와 2를 하나를 사용해 만든 2를 나눈 값인 22 // 2 = 11이다.

위와 같은 DP 방식으로 원하는 답을 얻어낼 수 있다.

def solution(N, number):
    sets = [set()] # 인덱스(i) 개의 N을 사용해서 만들 수 있는 숫자들을 저장할 집합의 배열 선언, 0개의 N을 사용해서 만들 수 있는 수는 없음
    
    for i in range(1, 9): # N을 1개 사용하는 경우부터 8개를 사용하는 경우까지 반복
        temp = set([int(str(N)*i)]) # N을 연속으로 i개 사용하는 경우를 집합에 저장
        for j in range(1, i): # j는 0 < j < i인 정수
            for x in sets[i-j]:
                for y in sets[j]:
                	# N을 i개 사용해서 만들 수 있는 수 = (N을 i-j개 사용해서 만들 수 있는 수) (+, -, *, //) (N을 j개 사용해서 만들 수 있는 수)   
                    temp.add(x + y)
                    temp.add(x - y)
                    temp.add(x * y)
                    if y != 0: # y가 0이면 나누기 skip
                        temp.add(x // y)
            
        if number in temp: # 만약 원하는 수가 N i개를 사용해서 만들 수 있는 수의 집합 안에 들어있다면
            return i # 정답은 i
        sets.append(temp) # N을 i개 사용해서 만들 수 있는 집합을 sets에 저장하여 다음 연산 시에 사용할 수 있도록 함
    
    return -1 # N을 8개까지 사용해도 number를 만들 수 없다면 -1을 반환