문제 설명
아래와 같이 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입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.
알고리즘
이게 Dynamic Programming으로 푸는 문제라고는 생각이 들었는데, 어떻게 세부 문항으로 쪼개야 할지 감이 오질 않았다. 덧셈 뺄셈만 사용한다면 쉬울텐데, 곱셈과 나눗셈, 심지어 괄호까지 사용이 되어야 한다고 하니 어떻게 시작을 해야할지 모르겠다.
처음에는 예시에 나온 12를 만드는 경우는 (1+11),(2+10),.....(6+6)이니까, 이 경우를 따져야 하나 생각을 했는데, 12의 최소값은60 / 5 였기 때문에 이 방법은 아니었다.
30분 정도 고민을 하다가 구글링의 도움을 조금 받기로 했다.
이 링크의 도움을 받았는데, 핵심은 이거였다.
-
최솟값이 8보다 크면 -1을 반환한다 => 결국 N은 최소 1번, 최대 8번 사용가능하다. N을 한번 쓰는 경우는 N이 되는 경우 밖에 없다.
그리고 8번 사용까지 반복문을 돌려도 number가 구해지지 않으면 -1을 return하면 된다. -
고로 N을 1번~8번 사용하는 집합 리스트를 만든다.
N을 한 번 사용한 값은s[1]에, 두 번 사용한 값은s[2]에 넣는 식으로. -
N을 두번 사용한 값에는 NN이 있고, N을 세번 사용한 값에는 NNN이 무조건 있다.( Ex : N = 5일 때, 55와 555와 같음.) 고로, 집합을 초기화 할 때 이 값들을 넣어주고 시작한다.
-
이 방법이 이 문제의 핵심 요소이다.
2번 집합 구성요소는(1번 집합) +-*/ (1번 집합)
3번 집합 구성요소는(1번 집합) +-*/ (2번 집합), (2번 집합) +-*/ (1번 집합)
4번 집합 구성요소는(1번 집합) +-*/ (3번 집합), (2번 집합) +-*/ (2번 집합), (3번 집합) +-*/ (1번 집합) -
계산 하다가, number가 발견 되면 즉시 집합 번호를 return 하면 된다.
정답 코드
def solution(N, number):
s = []
answer = 0
k = 0
for i in range(9):
if i >= 1: # 55, 555와 같은 수들을 넣어주기 위함.
k = k*10 + N
s.append([k])
if N == number:
answer = 1
return answer
s[0] = [0]
s[1] = [N] # N을 한번만 이용해서 만들 수 있는 수는 N밖에 없음.
for i in range(2,9): # 핵심 코드.
j = 1
while j<i:
for x1 in s[j]:
for x2 in s[i-j]:
s[i].append(x1 + x2)
s[i].append(x1 - x2)
s[i].append(x1 * x2)
if x2 != 0:
s[i].append((x1 / x2))
j = j+1
if number in s[i]: # 발견 되면 바로 탈출.
answer = i
return answer
s[i] = set(s[i]) # 집합 자료형을 이용하여 중복을 없애 메모리를 줄여준다.
answer = -1 # 끝까지 number를 구하지 못했음.
return answer고민을 굉장히 오래했지만, 내가 혼자서 풀지 못한 문제이다. Level 3이기 때문에 나중에 코딩테스트를 본격 준비하게 될 때 즈음에 한 번 더 풀어봐야겠다.
