1. 문제 설명
아래와 같이 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 함수를 작성하세요.
2. 제한 사항 및 입출력 예시
2.1 제한 사항
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
2.2 입출력 예
| N | number | return |
|---|---|---|
| 5 | 60 | 4 |
| 2 | 11 | 3 |
2.3 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
11 = 22/2 와 같이 2를 3번만 사용하여 표현할 수 있습니다.
3. 해설
이 문제를 어떻게 동적 계획법으로 접근해야 되는지 감이 잘 안 올 수도 있다. 하지만 그럴 때마다 동적 계획법의 정의를 다시금 떠올려보고 작은 해집합부터 접근해보자.
동적 계획법(Dynamic Programming): 하나의 문제를 여러 개의 작은 문제로 나누어 해결하고, 그것들을 조합하여 문제를 풀어나가는 방법
우선, N이 5이고 목표 숫자가 60일때, N을 1번만 써서 어떤 숫자를 만들 수 있는지 생각해보자.
- cnt = 1, num = 5
그렇다. 숫자가 하나밖에 없는데 하나 가지고 뭘 한단 말인가. 그 다음은 cnt = 2일 때를 생각해보자.
- cnt = 2, num = 5+5, 5-5, 5*5, 5/5, 55
여기서 느낌이 올 것이다. 숫자 2개를 이어붙인 것과, 앞서 구한 cnt = 1일 때의 숫자를 사칙연산한 결과다. 그렇다면 cnt = 3일 때는 어떨까?
- cnt = 3, num = 555, (5+5)+5, (5+5)-5, (5+5)*5, (5+5)/5, ...
cnt = 3일 때의 숫자는 cnt = 1의 숫자와 cnt = 2의 숫자를 사칙연산한 집합이라고 말할 수 있다. 우리는 이 문제의 점화식을 다음과 같이 표현할 수 있다
DP[n] = (DP[0], DP[n-1]) + (DP[1], DP[n-2]) + ... + (DP[i], DP[n-i-1]) + ... 이런 방식으로 차근차근 구하다가 number와 같은 수가 있으면, 그 때의 cnt값을 return해주면 끝. 점화식도 구했겠다, 이제 코딩할 일만 남았다.
4. 코드
def solution(N, number):
answer = 0
dp = []
for i in range(1, 9): #최대 8번의 반복 수행
dp.append({int(str(N)*i)})
if N==number: #N과 number가 같을 경우
return 1
for i in range(1, 8):
for j in range(i):
for num1 in dp[j]:
for num2 in dp[i-j-1]:
dp[i].add(num1+num2)
dp[i].add(num1-num2)
dp[i].add(num1*num2)
if num2 != 0:
dp[i].add(num1//num2)
if number in dp[i]:
return i+1
return -1 #최소값이 8보다 클 경우 -1 return.jpg)