[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	retrun
5	12	4
2	11	3

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

---

풀이

N의 범위가 제한되어 있어서 DP 문제라는 생각이 찌르르 왔다. 그런데 규칙을 찾는 게 어려웠던 문제이다.

number을 N을 사용해서 표현한다고 접근하지 말고
N을 M번 사용해서 number을 만들었으니 역추적하자고 접근

'''
숫자 N과 사칙연산을 최소 몇 개 사용해서 number을 표현할 수 있는 가
N = 2일 때 22/2 처럼 22, 222.. 도 가능 
만약 연속이 안 됐다면 number%N + number//N이었을 텐데 (아님. 이건 +, /만 사칙연산이라고 생각할 때고, -, * 포함해야함)

DP인 것 같은데 시작 케이스를 N을 기준으로 해야 할지, number을 기준으로 할 지(작은 문제 정의하기)
=> N을 1개 사용, 2개 사용, 3개 사용.. 해서 표현할 수 있는 경우
=> 1부터 9 사이의 N을 사용해서 만들 수 있는 수 집합을 미리 구하고, number이 처음 나올 때를 리턴 
'''

def solution(N, number):
    answer = -1
    dp =  [set() for i in range(9)] # N을 i번 사용해서 표현할 수 있는 숫자를 담는 리스트
    # [set(), set(), set(), set(), set(), set(), set(), set(), set()]
    
    for i in range(1,9): # i는 N의 개수
        num = int(str(N)*i) # {N}, {NN}, {NNN}...
        dp[i].add(num)
        for j in range(i//2+1):
            for op1 in dp[j]:
                for op2 in dp[i-j]:
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op2 - op1)
                    dp[i].add(op1 * op2)
                    if op2 != 0:
                        dp[i].add(op1 // op2)
                    if op1 != 0:
                        dp[i].add(op2 // op1)
        if number in dp[i]:
            return i
    return -1

- 리스트 dp는 인덱스가 i일 때 연산횟수가 i일때에 가능한 숫자를 담는다. set을 사용한 이유는 중복 없이 숫자를 담을 수 있고, in 탐색이 빠르기 때문이다.
- i가 5일때 (1,4), (2,3)의 경우를 사칙연산해야 하기 때문에 (여기서 1은 연산 횟수가 1일 때 가능한 숫자 집합) j의 범위는 i//2까지이다.
- 0으로 나누지 않게 조심한다. 덧셈과 곱셈은 op1, op2 순서가 달라져도 같은 값이 나오지만, 나눗셈과 뺄셈은 그렇지 않다.
- 하나의 i에 대한 작업이 끝날 때마다 number가 표현될 수 있는 지 확인한다.

 

규칙 찾기

2개를 사용해서 표현할 때는 (55와 같이 단순히 이어붙인 경우를 제외하고) 1개를 사용한 경우의 수와 1개를 사용한 경우의 수를 사칙연산했다.
3개를 사용해서 표현할 때는 (이어 붙인 경우 제외) 1개를 사용한 경우의 수와 2개를 사용한 경우의 수를 사칙연산했다.

이를 일반화하면 N을 M번 이어붙여서 만든 수는
N을 1번 사용해서 표현한 수에 M-1번 사용해서 표현한 수를 사칙연산하는 경우
+ N을 2번 사용해서 표현한 수에 M-2번 사용해서 표현한 수를 사칙연산하는 경우
+ ...
+ N을 M//2번 사용해서 표현한 수에 M//2번 사용해서 표현한 수를 사칙연산하는 경우

📝
List의 각 원소를 set으로 선언하기도 가능하다

dp =  [set() for i in range(9)] # N을 i번 사용해서 표현할 수 있는 숫자를 담는 리스트
#[set(), set(), set(), set(), set(), set(), set(), set(), set()]

string으로 수를 이어 붙인 뒤 int로 변환

num = int(str(N)*i) # {N}, {NN}, {NNN}...
twentyfour = int(str(2)+ str(4))

참고     참고2