Level 3
문제
정답
def solution(N, number):
if number == 1:
return 1
set_list = []
for cnt in range(1, 9): # 1개부터 8개까지 확인
# 1. [ SET x 8 ] 초기화
partial_set = set() # 2. 각 set마다 기본 수 "N" * i 수 초기화
# 3. n 일반화
# {
# "n" * i U
# 1번 set 사칙연산 n-1번 set U
# 2번 set 사칙연산 n-2번 set U
# ...
# n-1번 set 사칙연산 1번 set,
# }
# number를 가장 최소로 만드는 수 구함.
partial_set.add(int(str(N) * cnt)) # 이어 붙여서 만드는 경우 넣기
for i in range(cnt - 1): # (1, n-1) 부터 (n-1, 1)까지 사칙연산
for op1 in set_list[i]:
for op2 in set_list[-i - 1]:
partial_set.add(op1 + op2)
partial_set.add(op1 * op2)
partial_set.add(op1 - op2)
if op2 != 0:
partial_set.add(op1 // op2)
# 만든 집합에 number가 처음 나오는지 확인
if number in partial_set:
return cnt
set_list.append(partial_set)
return -1
풀이
문제의 변수 파악
N의 개수를 알아야 한다.
가장 작은 문제
최솟값이 8보다 크면 -1을 return 하기 때문에 N을 8개까지 써서 표현할 수 있는 집합을 구해보고자 한다!
- N을 1개 사용해서 표현할 수 있는 수의 집합은?
- N을 2개 사용해서 표현할 수 있는 수의 집합은?
- N을 3개 사용해서 표현할 수 있는 수의 집합은?
- N을 4개 사용해서 표현할 수 있는 수의 집합은?
...- N을 8개 사용해서 표현할 수 있는 수의 집합은?
ex) N을 5라고 가정
N을 1개 사용해서 표현하기
=> 5
(표현할 수 있는 수 1개)
N을 2개 사용해서 표현하기
=> 55
=> 5 + 5
=> 5 - 5
=> 5 / 5
=> 5 * 5
(표현할 수 있는 수 5개)
[1번 사용해서 표현한 수)]와[1번 사용해서 표현할 수 있는 수를 사칙 연산] 한 묶음이다.
N을 3 사용해서 표현하기
=> 555
=> 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를 3번 사용해서 만들 수 있는 수 (여기서, U는 합집합을 나타냅니다.) :
555 U
(1번 SET 과 2번 SET 사칙연산한 결과 값들) U
(2번 SET 과 1번 SET 사칙연산한 결과 값들)
2를 사칙연산으로 나타내보자
2 = 2
= 1 + 1
3을 사칙연산으로 나타내보자
3 = 3
= 1 + 2
= 2 + 1 (= 1 + 1 + 1)
4를 사칙연산으로 나타내보자
4 = 4
= 1 + 3
= 2 + 2
= 3 + 1
일반화
N을 n번 이어 붙여서 만든 수
N을 1번 사용해서 표현한 수 집합 (사칙 연산) n - 1 번 사용해서 표현한 수 집합
N을 2번 사용해서 표현한 수 집합 (사칙 연산) n - 2 번 사용해서 표현한 수 집합
.
.
.
N을 n - 1번 사용해서 표현한 수 집합 (사칙 연산) 1 번 사용해서 표현한 수 집합
N을 n번 사용해서 만들 수 있는 수 :
N을 n번 연달아서 사용할 수 있는 수 U
N을 1번 사용했을 때 SET 과 n-1번 사용했을 때 SET을 사칙연산한 수들의 집합 U
N을 2번 사용했을 때 SET 과 n-2번 사용했을 때 SET을 사칙연산한 수들의 집합 U
... U
N을 n-1번 사용했을 때 SET 과 1번 사용했을 때 SET을 사칙연산한 수들의 집합
이 문제는 즉, 1~8번까지 순회해서 만들어지는 수들의 집합 속에 number가 있는 최소 수를 찾아내기만하면 된다.
