숫자 N과 target인 number 만 주어졌을 때
N을 이용한 사칙연산을 통해 target인 number를 만드는데,
거기다가 표현할 수 있는 방법중 N사용 횟수의 최솟값을 return 하라니
아주 신박한 문제라고 느껴졌다.
ex)
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
12는 5를 통해 이렇게 3가지 사칙연산을 이용해 구할 수 있는데 이 중 마지막 방법이 5를 4개 사용하여 가장 최소로 쓴 식이라 여기선 4를 return 해주면 옳은 답이 된다.
흠
어떻게 풀 수 있을까
추가로, 문제에서 제시한 제한 사항은 다음과 같다.
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
3에서 나머지는 무시하고 몫만 가져온다는 점과,
4에서 return값이 8보다 크면, -1을 return 해야한다는 점 등의 특이사항이 있다.
사실 이 문제의 유형이 DP(동적계획법) 임을 알고 있어서 DP로 풀어야겠다. 마음가짐이 들지만 모르고 그냥 돌입했다면, DP로 풀 생각을 못했을 것 같다.
그렇다면 DP로 어떻게 풀어야 할까
생각난 방법은
이 return 해주는 N의 개수 값을 1부터 차근차근 올려보며 가능한지 dp배열에 저장하는 것이다.
dp[1] 에 N을 하나만 써서 number에 접근이 가능한 지 해보고
dp[2] 에 N을 두개 써서 number에 접근이 가능한 지 해보고
그렇게 해서 dp[8]까지 했는데 만약 접근이 다 가능하지 않다?
그러면 -1을 return 해주는 것이다.
그럴싸하다. 이 방법대로 더 깊이 파보겠다.
음.. 그런데 이 방법은 dp 가 아니라 그냥 배열에 값을 저장하는 방법이다.
dp는 캐싱 느낌으로 불필요한 연산을 앞에서 이미 저장한 값으로 생략하는게 포인트인데 말이다.
.
.
.
해답은 이거였다.
dp[k] 를 N을 k번 사용해서 만들 수 있는 모든 값들의 집합(Set) 놓는 것.
무슨 말이냐,
예를 들어, N=5라고 할 때
dp[1] = 5를 '1'번 사용해서 만들 수 있는 모든 값들의 집합 ! 즉 {5} 하나.
dp[2]는? 5를 '2번' 사용해서 만들 수 있는 모든 값.
- 연결수(concat) : {55}
- 사칙연산 : 5+5=10, 5-5=0, 5*5=25, 5//5=1
⇒ {55, 10, 0, 25, 1}
dp[3]은? 5를 '3'번 사용해서 만들 수 있는 모든 값
- 연결수(concat) : {555}
- 사칙연산 :
분할 조합: i + (k-i) 로 나눠서
dp[i]와 dp[k-i]의 원소들을 사칙연산으로 조합
i=1, k-i=2 → dp[1] × dp[2]
사칙연산
- 5 + {55,10,0,25,1} = {60,15,5,30,6}
- 5 - {55,10,0,25,1} = {-50,-5,5,-20,4}
- 5 * {55,10,0,25,1} = {275,50,0,125,5}
- 5 // {55,10,0,25,1} (0 제외) = {0,1,5}
i=2, k-i=1 → dp[2] × dp[1]
사칙연산
- {55,10,0,25,1} + 5 = {60,15,5,30,6}
- {55,10,0,25,1} - 5 = {50,5,-5,20,-4}
- {55,10,0,25,1} * 5 = {275,50,0,125,5}
- {55,10,0,25,1} // 5 (0 제외) = {11,2,0,5,0}
=> 총 조합
dp[3] = {555, 60, 15, 5, 30, 6, -50, -5, -20, 4, 275, 50, 0, 125, 11, 2, 20, -4, 1}
이런 식으로 dp[k]를 채워나가며, 매번 target인 number가 있으면 즉시 k를 return한다.
구현 방식
- 연결수(concat)
- int(str(N) * k)
- ex) N=5 → k=1: 5, k=2: 55, k=3: 555
- 사칙연산 조합
- k를 i와 (k-i)로 쪼갠다.
- a ∈ dp[i], b ∈ dp[k-i] 에 대해
- a+b, a-b, a*b, a//b(b≠0) 를 모두 dp[k]에 넣는다.
- 조기 종료
- 각 단계에서 number가 발견되면 바로 k를 return
- 8까지도 없으면 -1 반환
해답 및 풀이
def solution(N, number):
# N을 아무것도 안했는데 number와 같다면, 바로 1 return
if N == number:
return 1
dp = [set() for _ in range(9)] # 2차원 dp 배열, 안에 set()자료형이 0부터 인덱스 8 까지 들어감
# dp = [
# set(), # dp[0] N 0개로 만들 수 있는 값들
# set(), # dp[1] N 1개로 만들 수 있는 값들
# set(), # dp[2] N 2개로 만들 수 있는 값들
# ...
# set() # dp[8] N 8개로 만들 수 있는 값들
# ]
for k in range(1,9):
# 1) 연결수
concat = int(str(N) * k)
dp[k].add(concat) # 집합이라 add 함수 사용
# 2) 사칙연산 조합
for i in range(1, k):
for a in dp[i]:
for b in dp[k - i]:
dp[k].add(a + b)
dp[k].add(a - b)
dp[k].add(a * b)
if b != 0 :
dp[k].add(a // b)
# 타겟인 number가 dp[k]안에 있다면 바로 k return
if number in dp[k]:
return k
return -1 # 반복문 다 돌았는데도 number가 안만들어진다면 -1 리턴dp문제는 dp 를 무엇으로 두는지가 항상 어려운 것 같다.
그 점을 잘 설계해보자
