[프로그래머스] 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 | return |
|---|---|---|
| 5 | 12 | 4 |
| 2 | 11 | 3 |
풀이
문제를 읽고 어떤 유형인지 추론하는 능력은 여전히 부족한 것 같다.
프로그래머스 고득점 Kit는 유형별로 나눠져있어 문제 유형을 알고 시작하기 때문에 문제를 푸는데 있어 조금더 수월해지긴 하지만, 문제 유형을 파악하는 능력을 기르는 훈련을 할 수는 없어서 살짝 아쉽다.
어쩔수없이 문제를 먼저 풀고 이를 다시 살펴보면서 이래서 이 유형이었다는 것을 추론하는 방식으로 진행하겠다.
이 문제는 Dynamic programming 유형의 Level 3 문제이다.
DP는 분할정복 기법에 Memorization을 가미한 것으로, 하나의 문제는 단 한번만 풀도록 하기 때문에 효율성이 좋은 알고리즘이다.
Memorization을 위한 배열의 행, 열, 성분을 구성하고 계산해 저장하는 것이 중요하다.
문제에서 제공된 정보를 간추려 행과 열, 그리고 그 안에 저장될 성분을 어떤걸로 할지 결정하면 좋다.
- N: 숫자
- number: 만들고자하는 숫자
- Return: N과 사칙연산만을 활용하여 number를 표현하기 위한 방법중 최솟값
먼저 각 열을 1부터 number로 한다고 생각해보자.
그때의 각 요소들은 각 열의 숫자를 만들기 위한 방법중 N을 최소로 사용한 방법의 N의 개수로 할 수 있을 것이다.
근데 이럴 경우 DP는 이전 결과값을 사용하여 다음 요소들을 계산해내야 하는데 이전 값들과 다음 값들의 관계가 없다는 것이 문제가 된다 (직접 나열해보면 무슨말인지 알 것 이다).
이번엔 1부터 8까지의 N의 사용횟수를 열로 한다고 생각해보자.
그때의 각 요소는 N을 열 번호만큼 사용했을 때 만들 수 있는 모든 수의 집합이 될 것이다.
예를들어 열번호 1번의 성분은 [5]가 된다.
열번호 2번의 성분은 [55, 5+5, 5-5, 5/5, 5*5]가 된다.
이런식으로 1부터 8까지의 N의 사용횟수를 열로 설정하면 이전 열의 성분과 주어진 숫자 N의 사칙연산을 통해 다음 열에 들어갈 값들을 계산해낼 수 있다.
다만 여기서 주의해야할 점은 예를들어 DP[4]에 들어가야할 모든 요소는 [DP[3]과 N의 사칙연산] 뿐만 아니라 [DP[3]과 N의 사칙연산, DP[2]와 DP[2]의 사칙연산]이어야 한다는 것이다.
왜냐면 “DP[3]과 N의 사칙연산”과 “DP[2]와 DP[2]의 사칙연산”은 서로 다른 수를 만들어내기 때문이다 (나는 이 부분을 극복하지 못해 아래 코드를 참고하였다.).
이게 바로 이 문제에서 DP를 써야하는 이유이다.
- N을 i번 사용하여 표현할 수 있는 수는 굉장히 많다.
- 모든 경우를 매번 계산해낼수도 있겠지만 이전의 결과들을 저장해서 사용한다면 효율적으로 N을 i+1번 사용하여 표현할 수 있는 수를 계산해낼 수 있다.
이런식으로 매 열 성분을 채우면서 number와 같은 수가 만들어졌는지 확인하고, 만들어졌으면 그때의 열번호를 반환하면 된다.
만약 8까지의 열을 채우는 동안 값이 return 되지 않았다면 number를 표현하기 위해 N이 8번 초과하여 사용되어야한다는 소리이기 때문에 이때는 문제 조건에 따라 -1을 반환하면 된다.
이를 코드로 작성하면 아래와 같다. Link
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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) # 같은 숫자 반복되는 거 하나를 추가한다.
case_set.append(basic_num)
for i_half in range(1, i//2+1): # 사용되는 숫자의 횟수를 구해야 하는데, 절반 이상으로 넘어가면 같은 결과만 나올 뿐이므로 절반까지만을 사용한다.
print(i, i_half, i-i_half)
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을 출력한다.