728x90
https://school.programmers.co.kr/learn/courses/30/lessons/42895
문제 유형 : dp를 베이스로 하는 완전 탐색
문제 풀이 : 숫자 n개를 이용해 만들기 위해선, 숫자 n-1개로 만든 수들을 이용해야 한다.
유의점 : N=4, number = 17 인 경우
-> 17 = (4*4) + (4/4)
이 경우는, 4를 4개를 이용해 17을 만들었는데, 4를 3개 이용한 조합에서 사칙연산한 것이 아니라,
4를 2개 이용한 숫자(= 4*4)와 4를 2개 이용한 숫자(= 4/4)를 이용해 답을 구한 것이다.
즉, 단순히 숫자 n개를 이용한 수를 만들기 위해선 n-1개로 만든 수에다가 추가로 사칙연산 하는 방법 이외에도
1개 + n-1개
2개 + n-2개
...
n-1개 + 1개
와 같은 다양한 조합들을 고려해야 한다.
def solution(N, number):
answer = -1
sign = 1
breaker = False
dp = [[] for _ in range(10)]
# N 사용 횟수가 8보다 크면 -1 return
for idx in range(1,9):
dp[idx].append(int(str(N)*idx))
if int(str(N)*idx) == number:
answer=idx
break
if idx != 1:
for i in range(1,idx):
for num1 in dp[i]:
for num2 in dp[idx-i]:
dp[idx].append(num1+num2)
dp[idx].append(num1-num2)
dp[idx].append(num1*num2)
if num2 > 0:
dp[idx].append(num1//num2)
if number in dp[idx]:
answer = idx
breaker=True
break
if breaker: break
return answer
728x90
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/C++] 입국심사 (0) | 2023.10.04 |
---|---|
[프로그래머스/파이썬] 가장 먼 노드 (0) | 2023.09.22 |
[프로그래머스/파이썬] 카펫 (0) | 2023.09.17 |
[프로그래머스/파이썬] 소수 찾기 (0) | 2023.09.16 |
[프로그래머스/파이썬] 큰 수 만들기 (0) | 2023.09.14 |