[프로그래머스] N으로 표현 - python

N으로 표현

문제 설명

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

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

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

풀이

문제를 처음 읽었을 때는 순열이나 백트래킹을 통해 풀 수 있을 것처럼 보인다. 하지만 시간복잡도에 맞춰서 해결할 수 없을 것 같기 때문에 동적 계획법으로 해결할 수 있는지 확인해본다.

작은문제 정의 하기

문제의 목표는 N을 최소로 사용해서 number를 만드는 것이 목표이다. 즉 N의 개수의 최소값을 구하는 게 목표이다.

따라서 작은 문제도 N의 개수로 정의한다.

 

N을 1개 사용해서 표현할 수 있는 수의 집합은?

N을 2개 사용해서 표현할 수 있는 수의 집합은?

N을 3개 사용해서 표현할 수 있는 수의 집합은?

N을 4개 사용해서 표현할 수 있는 수의 집합은?

.

.

N을 8개 사용해서 표현할 수 있는 수의 집합은?

작은 문제로 큰 문제 해결할 수 있는지 확인하기

N이 5라고 생각해보자

 

N을 1개 사용해서 표현하기

5

N을 한 번 사용해서 표현할 수 있는 수는 1개이다.

 

N을 2개 사용해서 표현하기

55, 5 + 5, 5 - 5, 5 / 5, 5 * 5

N을 두 번 사용해서 표현할 수 있는 수는 5개이다.

2를 나타내보면 ,

2 = 2
  = 1 + 1

즉 (2번 사용해서 표현한 수)와 (1번 사용해서 표현할 수 있는 수를 서로 사칙 연산)한 묶음임을 알 수 있다.

 

N을 3개 사용해서 표현하기

555, 
55 + 5, 55 - 5, 55 / 5, 55 * 5
5 + 5 + 5, 5 - 5 - 5, 5 / 5 / 5, 5 * 5 * 5

3을 사칙연산으로 나타내보면,

3 = 3
  = 1 + 2
  = 2 + 1 (= 1 + 1 + 1)

이를 일반화 해보면

n번 이어 붙여서 만든 수 
1번 사용해서 표현한 수 집합 (사칙 연산) n - 1 번 사용해서 표현한 수 집합
2번 사용해서 표현한 수 집합 (사칙 연산) n - 2 번 사용해서 표현한 수 집합
                    	.
                        .
                        .
                    
n - 1번 사용해서 표현한 수 집합 (사칙 연산) 1 번 사용해서 표현한 수 집합

의 합이 N을 n번 사용해서 표현할 수 있는 수의 집합임을 알 수 있다. 이 집합 중에 만들고자 하는 수 number가 있다면 N을 최소로 사용해서 표현할 수 있는 개수는 n이 된다.  즉 1 ~ 8개의 N을 사용해서 만들 수 있는 수의 집합 중에 number가 처음 나오는 개수를 리턴하면된다.

def solution(N, number):
    if number == 1:
        return 1
    set_list = []
    
    for cnt in range(1, 9): # 1개부터 8개까지 확인
        partial_set = set()
        partial_set.add(int(str(N) * cnt)) # 이어 붙여서 만드는 경우 넣기
        for i in range(cnt - 1): # (1, n-1) 부터 (n-1, 1)까지 사칙연산
            for op1 in set_list[i]:
                for op2 in set_list[-i - 1]:
                    partial_set.add(op1 + op2)
                    partial_set.add(op1 * op2)
                    partial_set.add(op1 - op2)
                    if op2 != 0:
                        partial_set.add(op1 / op2)
        # 만든 집합에 number가 처음 나오는지 확인
        if number in partial_set:
            return cnt
        set_list.append(partial_set)
    return -1