문제 설명
아래와 같이 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 합니다.
<코드>
def solution(N, number):
if N == number:
return 1
dp = [set() for _ in range(9)] # dp[i]는 N을 i번 사용해서 만들 수 있는 수의 집합
for i in range(1, 9):
dp[i].add(int(str(N) * i)) # N, NN, NNN, ... 같은 수를 추가
for j in range(1, i):
for op1 in dp[j]:
for op2 in dp[i-j]:
dp[i].add(op1 + op2)
dp[i].add(op1 - op2)
dp[i].add(op1 * op2)
if op2 != 0:
dp[i].add(op1 // op2)
# 목표 숫자가 있는지 확인
if number in dp[i]:
return i
return -1
<풀이과정>
- DP 배열 초기화:
- dp[i]: i번의 N 사용으로 만들 수 있는 모든 숫자의 집합
- 예를 들어, dp[1]에는 N, dp[2]에는 NN(55) 등의 숫자가 포함될 수 음
- 숫자 조합:
- dp[i]는 작은 부분 집합 dp[j]와 dp[i-j]를 사용해 만들 수 있는 숫자들로 구성
- 예를 들어, dp[3]은 dp[1]과 dp[2]를 조합하여 만들 수 있는 모든 수의 집합
- 탐색:
- dp[1]부터 시작, dp[8]까지의 집합을 생성하면서 number를 만들 수 있는지 확인
- 이 과정에서 number를 만들 수 있으면 사용 횟수를 반환
- 조기 종료:
- 만약 dp 배열의 어느 단계에서라도 number를 발견하면 그때의 사용 횟수 반환
- 8번의 사용으로도 number를 만들 수 없으면 -1 반환
'2024 코딩테스트 스터디' 카테고리의 다른 글
[13주_3일차] 프로그래머스-등굣길(Python) (0) | 2024.08.29 |
---|---|
[13주_2일차] 프로그래머스-정수 삼각형(Python) (0) | 2024.08.28 |
[12주_7일차] 프로그래머스-퍼즐 조각 채우기(Python) (0) | 2024.08.26 |
[12주_6일차] 프로그래머스-여행경로(Python) (0) | 2024.08.25 |
[12주_5일차] 프로그래머스-아이템 줍기(Python) (0) | 2024.08.25 |