[백준] 5557번 1학년 - python 파이썬

문제

 

 

 

 

처음 이 문제를 접했을 때는 dfs로 풀어주려고 했지만 범위를 자세히 보면 dfs로 구현할 시 시간초과가 발생한다는 것을 알 수 있다.

 

그래서 이를 해결하고자 DP를 사용해서 문제를 해결 해주었다.

 

2차원 배열의 dp를 통해서 i번째 인덱스에서 0~20 사이의 숫자중 가능한 경우의 수를 dp[i-1]에 저장된 수를 더해서 작성해주면 된다. 

 

 

 

 

 

따라서 i번째 인덱스에서 j라는 숫자를 만드는 경우의 수를 구해 나가는 방식으로 생각하면 된다

 

 

 

코드

n = int(input())
nums = list(map(int,input().split()))
dp = [[0]*21 for _ in range(n-1)]
dp[0][nums[0]] = 1

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

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