📖프로그래머스 - 고득점 kit - 동적계획법 - N으로 표현
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (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 | return |
|---|---|---|
| 5 | 12 | 4 |
| 2 | 11 | 3 |
입출력 예 설명
예제 #1문제에 나온 예와 같습니다.
예제 #211 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.
🔍Institution
- Dynamic programming이란?
크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어 해결한 뒤에 처리하여 나중에 전체의 답에 구하는 것. 분할정복과 같음 이때 memorization이 사용된다는 점이 분할 정복과 다름
→ 이미 계산한 결과는 배열에 저장
memorization을 통해 하나의 문제는 단 한번만 풀도록 하는 효율적인 알고리즘. 즉, 나중에 다시 풀 필요가 없음
- 여기서 dp에 무엇을 저장해야 할지가 dp문제의 핵심이다!
dp에는 어떤 값이 저장될 수 있을지, 나열해보았다.
5
55, 5+5, 5-5, 5/5, 5*5
| 55 | |
|---|---|
| 5 | +5, -5, /5, *5 |
555, 55+5, 555, 55/5, 55-5, 555, 5/55, 5+5*5, 5+5+5,
| 555 | |
|---|---|
| 55 | +5, -5, /5, *5 |
| 5+5 | +5, -5, /5, *5 |
| 5-5 | +5, -5, /5, *5 |
| 5/5 | +5, -5, /5, *5 |
| 5*5 | +5, -5, /5, *5 |
5555
| 5555 | |
|---|---|
| 555 | +5, -5, /5, *5 |
| 55 | +5, -5, /5, *5 |
| 55+5 | +5, -5, /5, *5 |
| 55-5 | +5, -5, /5, *5 |
| 55/5 | +5, -5, /5, *5 |
| 55*5 | +5, -5, /5, *5 |
dp[0] = 0
dp[1] = [5]
dp[2] = [510+5, dp[1] +-/]
dp[3] = [5100+510+5, dp[2]+-*/
…
dp[1] = [N]
| dp[2] = [NN, N+N, N-N, N*N, N/N] | dp[2] = [Ni, dp[1]+-/ dp[1] |
| dp[3] = [NNN, N + (N+N), N -(N+N… | dp[3] = [Ni, dp[1] +-/ dp[2]] |
dp[i] = [N * i, dp[i - 1] +-/* dp[i-2]
이걸 다 돌면서, 주어진 number값과 같은지 비교한다. 사용횟수를 1부터 확인하기 때문에 같은 값이 나온다면 그 값이 최소가 된다.
| dp (i = 사용 횟수) | 0 | 1 | 2 | … | i | ||
|---|---|---|---|---|---|---|---|
| N | [NN, N+N, N-N, N*N, N/N] | dp[2] = [Ni, dp[1]+-/ dp[1] | [NNN, N + (N+N), N -(N+N… | dp[3] = [Ni, dp[1] +-/ dp[2]] | … | [N * i, dp[i - 1] +-/* dp[i-2] |
바로 return 하면 최소가 됨
🔍Approach
🚩My submission
일단 코드가 빈약한 것처럼, 내 코드는 정상 실행이 되지 않는다…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(N, number):
answer = 0
dp = [[0] * i for i in range(1, N+1)]
dp[0] = N
for i in range(1, 10): # 바깥 for loop의 범위는 제한사항 참고하기 (제한사항 >> N은 1이상 9이하)
dp[i].append(int(str(dp[i-1]) + str(N)))
for j in range(1, N+1):
dp[i].append(dp[i-1] + N)
dp[i].append(dp[i-1] - N)
dp[i].append(dp[i-1] * N)
dp[i].append(dp[i-1] // N)
if dp[i][j] == number:
answer = j
return answer
다 못 풀었다… 그래서 다른 사람의 풀이를 참고하였다.
🚩Others submission
dp 리스트는 아래와 같이 저장한다.
| 횟수 | 1 | 2 | 3 | 4 | 5 | | — | — | — | — | — | — | | | 5 | 5 + 5, 5 - 5, 5 / 5, 5 * 5 55 | 5 사용횟수가 1일때와 2일 때의 각 케이스를 사칙연산한 것 | 5 사용횟수가 1일때와 3일 때의 각 케이스를 사칙연산한 것 + 5 사용횟수가 2일때와 2일 때의 각 케이스를 사칙연산한 것 | 5 사용횟수가 2일때와 3일 때의 각 케이스를 사칙연산한 것 + 5 사용횟수가 1일때와 4일 때의 각 케이스를 사칙연산한 것 |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(N, number):
possible_set = [0,[N]] # 조합으로 나올수 있는 가능한 숫자들, 여기에 계속 append하며 이후에 사용함
if N == number: #주어진 숫자와 사용해야 하는 숫자가 같은 경우는 1개면 족하므로 1으로 놓는다.
return 1
for i in range(2, 9): # 2부터 8까지로 횟수를 늘려 간다.
case_set = [] # 임시로 사용할 케이스 셋, 각 I 별로 셋을 만들어 possible set에 붙인다.
basic_num = int(str(N)*i) # 같은 숫자 반복되는 거 하나를 추가한다. ex) 5 55 555
case_set.append(basic_num)
for i_half in range(1, i//2+1): # 사용되는 숫자의 횟수를 구해야 하는데, 절반 이상으로 넘어가면 같은 결과만 나올 뿐이므로 절반까지만을 사용한다.
for x in possible_set[i_half]:
for y in possible_set[i-i_half]: # x와 y를 더하면 i 가 되도록 만든 수다.
#print(possible_set)
case_set.append(x+y)# 각 사칙연산 결과를 더한다.
case_set.append(x-y)
case_set.append(y-x)
case_set.append(x*y)
if y !=0:
case_set.append(x/y)
if x !=0:
case_set.append(y/x)
if number in case_set:
return i
possible_set.append(case_set) # 최종 결과물 set에 사칙 연산 결과를 더한다.
return -1 #N 이 8까지 답이 없으면 -1을 출력한다.
💡TIL
- 어떤 방식으로 접근해야 하는지, dp에는 무엇을 저장해야 하는지 까지는 접근을 잘 했는데, 코드를 짜는 것이 어려웠다.
- 이거는 다시 복습해야 할 것 같다.. 아직 이해를 못했다.