[백준/Boj] 5557 1학년 Python 풀이

https://www.acmicpc.net/problem/5557

5557번: 1학년

 

1) 시간초과 풀이

n = int(input())
array = list(map(int, input().split()))
answer = 0

def dfs(total, index, target):
    global answer
    if total < 0 or total > 20:
        return
    if index == n-1:
        if total == target:
            answer += 1
        return
    if 0 <= total <= 20:
        dfs(total+array[index], index+1, target)
        dfs(total-array[index], index+1, target)

dfs(array[0], 1, array[n-1])


print(answer)

2) dp 풀이 (통과)

2차원 배열로 dp값을 저장할 공간을 만든다. 

단 연산에서는 무조건 0 ~ 20까지의 숫자만 중간에 등장할 수 있으므로, dp 배열의 길이 또한 (인덱스 길이)*21 로 지정해 준다. 
연산을 할 때 첫번째 원소는 default값이 되어야 하며, 첫번째 원소는 항상 0 ~20 사이의 숫자일 것이므로 dp[0][array[0]] = 1 로 저장해준다. 

이말인 즉슨, 0번째 인덱스의 경우 array[0] 값을 만들 수 있는 경우는 1개 라는 정보이다. 

또한 dp[i-1][j] 를 확인해야 하는 이유는, 이전 계산 값이 0 ~ 20 범위를 초과하여 0 인경우, 고려하지 않아야 하기 때문이다. 

n = int(input())
array = list(map(int, input().split()))

dp = [[0]*21 for _ in range(n)] # index n 번째에 합이 k 가 될때 저장 dp[i][k], k 는 0 ~ 20
dp[0][array[0]] = 1 # 맨 처음 array 원소

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

print(dp[n-2][array[n-1]])

어렵지만 재밌는 dpdp