[Kakao] 타겟넘버

안뱅·2022년 6월 2일
0

[Coding Test]

목록 보기
8/35
post-thumbnail

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스는 좋으면서 나쁜게 문제별로 유형이 무엇인지 알려준다.
해당 문제는 DFS/BFS 유형의 문제라고 표기되어있다. 문제 유형을 본이상 당연히 DFS/BFS로 풀려고 하였으나, 아무리 봐도 해당문제를 왜 DFS/BFS로 풀어야하는 이유(효율성이나 복잡성 측면에서)를 모르겠어서
Dynamic Programming으로 solution을 구현했다.

풀이1

Solution1 : DP - 2차원

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

Solution2 : DP 1차원

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

0개의 댓글