N으로 표현
문제링크
https://programmers.co.kr/learn/courses/30/lessons/42895
풀이
일단 문제의 포인트는 문제에서 최솟값이 8보다 크면 -1을 return 합니다. 라고 했다. 즉 숫자 1개인 그룹에서 ~ 8개인 그룹만 신경쓰면 된다. 그런데 생각해보면 숫자 1개인 그룹 ~ 숫자 8개인 그룹은 아래와 같이 두개의 그룹을 조합해서 설명할 수 있다.
1
2
3
4
5
6
7
8
# 1 : (1)
# 2 : (0+2, 1+1)
# 3 : (0+3, 1+2)
# 4: (0+4, 1+3, 2+2)
# 5: (0+5, 1+4, 2+3)
# 6 : (0+6, 1+5, 2+4, 3+3)
# 7 : (0+7, 1+6, 2+5, 3+4)
# 8 : (0+8, 1+7, 2+6, 3+5, 4+4)
숫자가 2개 사용할 때, (N=5일때) [[55], [5, 5]] 이고 숫자 3개 사용할 때는 [[555], [5, 55]] 이런 식으로 모든 경우를 따져볼 필요 없이 숫자의 규칙이 보인다. 그래서 위와 같이 찾는 그룹 (i 개수만큼 사용할때)는 이중 for문을 돌려서 찾으면 된다. 그리고 예를 들어 숫자 3개인 그룹을 찾는다고 생각했을 때 (1+2) 와 (2+1) 은 같은 그룹이므로 이를 위해 for문의 range 설정을 (i//2+1)로 설정해주어야 한다. 그리고 각각의 그룹들끼리 +,-,*,// 을 모두 해서 set으로 중복을 없애준다음 만약 찾는 number 값이 case에 존재할 경우 return 해주고 아닐때는 S에 append하여 다음 그룹으로 계속 넘어가서 같은 방식으로 연산하게 된다. 그리고 최근에 테스트 케이스가 추가되었는데, N=5, number=5 일 경우 3이 아닌 1이 출력되어야 한다. 따라서 가장 첫줄에 N==number일 경우 바로 1로 return 해주는 코드를 추가하였다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(N, number):
S = [0, {N}]
if N == number:
return 1
for i in range(2, 9):
case = {int(str(N)*i)}
for j in range(1, i//2+1):
for x in S[j]:
for y in S[i-j]:
case.add(x+y)
case.add(x-y)
case.add(y-x)
case.add(x*y)
if x != 0:
case.add(y//x)
if y != 0:
case.add(x//y)
if number in case:
return i
S.append(case)
return -1