[백준] 5557번 : 1학년

이번주는 다이나믹 프로그래밍 문제를 푸는 주 입니다. 지난주에는 그래프 이론 유형의 문제를 풀었는데요, 다이나믹 프로그래밍 문제를 풀어보니, 저는 그래프의 문제를 더 잘 푸는것 같습니다. 이번주에는 다이나믹 프로그래밍 유형을 열심히 익히도록 하겠습니다.

5557번: 1학년

5557번: 1학년

🤔 문제분석

처음에 문제를 접근할때에는 탑다운 방식으로 문제를 접근하였습니다. 저는 아직까지 탑다운 방식의 문제풀이가 더 쉽게 풀리는것 같습니다. 현재위치의 인덱스에서 덧셈과 뺄셈을 해보면서 범위값이 넘어가지 않는 경계한에서 재귀호출을 합니다. 인덱스가 마지막에 도달 했을때 원하는 값에 도달된경우를 1을 리턴하고, 그렇지 않은경우는 0을 리턴합니다.

“ 여기서 중요한점은 DFS 탐색이기때문에 끝까지 탐색을 완료한뒤, 탐색한 결과를 저장시켜놓은뒤 다른 계산식에서 접근할때 이미 계산된 값을 리턴해주어 시간복잡도를 단축 할 수 있습니다.

예를들어 5번째 인덱스에서 10인경우가 이미 마지막 인덱스까지 방문해서 5가지라고 한다면, 계산할 필요없이 이미 계산된 값을 리턴해줍니다.

📝 의사코드

1. 종료조건은 마지막인덱스를 방문할때 종료시킨다.
   1. 종료할때에 결과값이 원하는 결과값이라면 1을 리턴 그렇지 않다면 0을 리턴한다.
2. 재귀조건
   1. 더하기 ) 20≥ 현재 값 + 인덱스의 값
   2. 빼기 ) 현재값 - 인덱스의 값 ≥ 0
3. 이미 방문한 이력이 있다면 바로 개수를 리턴한다.

💻 코드

import sys
input = sys.stdin.readline
INF = pow(2, 63) -1
N = int(input())
nums = list(map(int, input().split()))

result = nums[-1]
nums.pop()
length = len(nums)
dp = [[-1 for _ in range(21)] for _ in range(length)]

def dfs(i, cur):
    if i == length-1:
        if cur == result:
            return 1
        else:
            return 0
    
    if dp[i][cur] != -1:
        return dp[i][cur]
    
    dp[i][cur] = 0
    if 20 >= cur + nums[i+1] >= 0:
        dp[i][cur] += dfs(i+1, cur + nums[i+1])
    if 20 >= cur - nums[i+1] >= 0:
        dp[i][cur] += dfs(i+1, cur - nums[i+1])
    
    return dp[i][cur] % INF

print(dfs(0, nums[0]))

🎯 피드백 및 개선사항

바텀업 방식으로도 문제를 해결해보았습니다.

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))
length = len(nums) - 1

dp = [[0 for _ in range(21)] for _ in range(length)]

dp[0][nums[0]] = 1

for i in range(1, length):
    for j in range(21):
        if dp[i-1][j]:
            if 20 >= j + nums[i]:
                dp[i][j+nums[i]] += dp[i-1][j]
            
            if j - nums[i] >= 0:
                dp[i][j-nums[i]] += dp[i-1][j]

print(dp[length-1][nums[-1]])