[BOJ] 5557 - 1학년 (Python)

 

 

아이디어

 

동적 계획법으로 중간 계산 결과가 0 이상 20 이하인 값들에 대한 경우의 수를 구해 나간다.

 

 

풀이

 

숫자의 개수를 N, 주어지는 숫자를 리스트 numbers에 입력 받는다.

0으로 채워진 (N-1)×21 크기의 2차원 리스트 dp를 생성하는데, dp[i][j]에는 i 번째 중간 계산 결과 j의 경우의 수를 저장한다.

처음 dp[0]의 첫 숫자의 위치에 1을 저장하고, for문에서 0 이상 20 이하의 중간 결과값의 경우의 수를 dp에 저장해 나간다.

마지막 계산 결과값이 주어진 마지막 숫자로 올바른 등식의 수 dp[-1][numbers[-1]]을 출력한다.

 

def solution():
    N = int(input())
    numbers = tuple(map(int, input().split()))
    dp = [[0]*21 for _ in range(N-1)]
    dp[0][numbers[0]] = 1
    for i in range(1, N-1):
        for j in range(21):
            if dp[i-1][j]:
                if j+numbers[i] <= 20:
                    dp[i][j+numbers[i]] += dp[i-1][j]
                if j-numbers[i] >= 0:
                    dp[i][j-numbers[i]] += dp[i-1][j]
    print(dp[-1][numbers[-1]])

solution()