문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165
프로그래머스는 좋으면서 나쁜게 문제별로 유형이 무엇인지 알려준다.
해당 문제는 DFS/BFS 유형의 문제라고 표기되어있다. 문제 유형을 본이상 당연히 DFS/BFS로 풀려고 하였으나, 아무리 봐도 해당문제를 왜 DFS/BFS로 풀어야하는 이유(효율성이나 복잡성 측면에서)를 모르겠어서
Dynamic Programming으로 solution을 구현했다.
1) numbers element를 통해서 얻을 수 있는 경우의 수
= 2 **len(numbers)2) dp table 길이를 2**len(numbers)로 초기화
3) 다음 계산 결과를 이전 dp table를 통해서 계산하고 결과값들 2차원 형태로 추가
4) numbers의 마지막 element 까지 계산하고 나면 dp의 마지막 리스트에서 target 개수 계산
def solution1(numbers, target):
answer = 0
dp = [[] for _ in range(2**len(numbers))]
dp[0].append(numbers[0])
dp[0].append(numbers[0]*(-1))
start = 1
level = 1
while level < len(numbers):
for i in dp[start-1]:
p_value = i + numbers[start]
dp[start].append(p_value)
n_value = i - numbers[start]
dp[start].append(n_value)
level += 1
start += 1
answer = dp[level-1].count(target)
return answer
1)solution1와 동일하나 dp table를 2차원이아닌 1차원으로 구성
2)1차원으로 구성시 next value를 계산하고 저장하는 과정에서 필요한 수식을 점화식을 구현
def solution2(numbers, target):
answer = 0
dp = [0.5 for _ in range(2**len(numbers))]
dp[0] = numbers[0]
dp[1] = numbers[0]*(-1)
level = 1
end = 2
while level < len(numbers):
for j in range(end,len(dp)):
if dp[j] == 0.5:
end = j
break
for i in range((end*2)-1, -1, -2):
dp[i] = dp[int((i-1)/2)] - numbers[level]
dp[i-1] = dp[int((i-1)/2)] + numbers[level]
level += 1
answer = dp.count(target)
return answer