[알고리즘] 타겟 넘버
2023. 7. 19. 09:05ㆍ알고리즘 풀이
문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
numbers target return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.
나의 풀이
- product를 쓰면 for문이 하나 더 들어가게 되므로 DFS, BFS를 썼을 때보다 느려질 수밖에 없다.
from itertools import product
def solution(numbers, target):
# 방법의 수를 구하는 문제
# 모든 경우의 수를 구하기 위해서는 탐색이 필요하다
# 숫자의 최대 개수가 20개이고 이때의 탐색에는 2^20가 있고 1024 * 1024 대략= 1,000,000이 된다
# 따라서 product를 써도 된다.
answer = 0
op_kind = ['-', '+']
for ops in product(op_kind,repeat=len(numbers)):
result = 0
for i, op in enumerate(ops):
if op == "-":
result -= numbers[i]
else:
result += numbers[i]
if result == target:
answer += 1
return answer
이건 dfs로 풀이한 것이다. 웬만해서는 dfs로 풀지 않지만 가야할 방향이 적은 것에 대해서는 쓸만한 듯하다.
def dfs(numbers, idx, cal, target):
ret = 0
if idx == len(numbers):
if cal == target:
return 1
else:
return 0
ret += dfs(numbers, idx+1, cal+numbers[idx], target)
ret += dfs(numbers, idx+1, cal-numbers[idx], target)
return ret
def solution(numbers, target):
return dfs(numbers, 0, 0, target)
Reference
https://school.programmers.co.kr/learn/courses/30/lessons/43165/solution_groups?language=python3
'알고리즘 풀이' 카테고리의 다른 글
[알고리즘][X] 게임 맵 최단거리 (0) | 2023.07.21 |
---|---|
[알고리즘] 네트워크 (0) | 2023.07.20 |
[알고리즘][X] 도둑질 (0) | 2023.07.18 |
[알고리즘][X] 등굣길 (0) | 2023.07.17 |
[알고리즘][X][RE] 사칙연산 (0) | 2023.07.16 |