백준: 5557 1학년

문제

5557번: 1학년

 

문제 풀이

 숫자가 주어 질 때, +, - 를 통해 숫자를 계산 할 수 있으며 계산된 숫자의 범위는 0 보다 크고, 20 보다 작아야 한다. 또한 주어진 숫자를 계산할 때, 마지막으로 주어진 숫자와 일치해야 한다. 예제 입력1의 경우 문제의 주어진 힌트와 같이 다음과 같은 경우의 수가 있다.

 

• 8+3-2-4+8-7-2-4-0+8=8
• 8+3-2-4+8-7-2-4+0+8=8
• 8+3+2+4-8-7+2-4-0+8=8
• 8+3+2+4-8-7+2-4+0+8=8
• 8+3+2-4+8-7+2+4-0-8=8
• 8+3+2-4+8-7+2+4+0-8=8
• 8-3+2+4-8+7+2+4-0-8=8
• 8-3+2+4-8+7+2+4+0-8=8
• 8-3+2-4+8+7+2-4-0-8=8
• 8-3+2-4+8+7+2-4+0-8=8

 이 경우의 수는 DFS를 통해 구할 수도 있지만, 2차원 배열을 이용하여 DP로 풀수도 있다. 이와 같은 문제는 이전에 다룬

기타리스트와 유사한 방식으로 풀면 된다. 다만 다른 점이 있다면 예제 입력 1의 경우 8이라는 값이 나오는 횟수를 출력해야 한다. 따라서 모든 숫자를 사용하여 계산하였을 때, 8이 되는 경우가 몇 개인지 중첩하면서 체크해야 한다.

 

'''
7 
8 3 2 4 8 7 2 
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0] 
[0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0] 
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0] 
[0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 0, 0, 1, 0, 1, 0, 1]
'''

 예를 들어 위와 같은 테스트 케이스를 실행한다면, 2차원 배열에 나타낼 수 있는 숫자들이 표시될 것이고, 2가 되는 경우의 수는 1개라는 것을 알 수 있다. 만약 8, 10, 12가 된다면 2가지의 경우의 수 가 있다는 것을 알 수 있다. 이와 같이 트리와 같은 구조로 탐색이 된다면 DFS를 통해 풀지 않고 2차원 배열을 사용하여 정답을 찾을 수 있다.

 

코드

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))
    dp = [[0] * 21 for _ in range(n - 1)]
    dp[0][nums[0]] = 1

    for i in range(1, n - 1):
        cur_num = nums[i]

        for j in range(21):
            if not dp[i - 1][j]:
                continue

            if j + cur_num <= 20:
                dp[i][j + cur_num] += dp[i - 1][j]

            if 0 <= j - cur_num:
                dp[i][j - cur_num] += dp[i - 1][j]

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