[문제풀이-백준] 5557. 1학년

풀이

DP

처음에 백트래킹을 이용해서 풀려고 했다. N이 100이기 때문에 재귀의 최대 깊이는 100이고 100*100으로 계산했다. 하지만 풀이 후 잘못 계산 했다는 것을 알았다. 더하고 뺴는 과정이 2개이고, 최대 100번 반복해야하므로 2^100이 된다. 따라서 시간 초과가 발생한다.

DP로 풀 수 있는 방법이 무엇이 있는지 생각해봤다. 더하면서 중복된 값이 존재할 수 있다는 것을 알았고, memoization을 이용해야겠다고 생각했다. 해당 숫자가 몇개 나왔는지 경우의 수를 들고 있는 것이다. 그런데 처음 개선했던 방법은 나온 수를 dp리스트에 넣고 정렬했다. 이 경우 매번 sort를 해야 하고 갯수를 세는 과정도 dp만큼 for문을 두번 돌아야 해서 비효율적이다.

참고했던 방법은 dp를 2차원 리스트로 만들고, 결과 값이 나온 수의 인덱스에 경우의 수를 넣는 것이다. 즉 첫번째 숫자는 무조건 1개이므로 dp[숫자][0]에 1을 넣는다. 이후, 1부터 N-2까지 진행하면서 dp의 값이 1이상(경우의 수가 있다)인 지점을 찾고 거기에서 더하고 뺀 값의 행에 넣어주는 것이다.

시간 복잡도

O(20n) = O(n)

코드

정답

DP

MAX_NUMBER = 20
N = int(input())
numbers = list(map(int,input().split()))
dp = [[0] * N for _ in range(MAX_NUMBER + 1)]
dp[numbers[0]][0] = 1
for col in range(1, N - 1):
    for row in range(MAX_NUMBER + 1):
        if dp[row][col-1]:
            plus = row + numbers[col]
            minus = row - numbers[col]
            if plus <= 20: dp[plus][col] += dp[row][col-1]
            if minus >= 0: dp[minus][col] += dp[row][col-1]

print(dp[numbers[-1]][N-2])

시간초과

백트래킹

def calculate(depth, sum_val):
    global answer
    if depth == N - 1:
        if sum_val == numbers[-1]: answer += 1
    else:
        plus_num = sum_val + numbers[depth]
        minus_num = sum_val - numbers[depth]
        if plus_num <= 20: calculate(depth + 1, plus_num)
        if minus_num >= 0: calculate(depth + 1, minus_num)

answer = 0
N = int(input())
numbers = list(map(int,input().split()))
calculate(0, 0)
print(answer)