[백준 - Python] 5557 - 1학년

0.  문제 링크

 

 

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

5557번: 1학년

---

1.  풀이 방법

 

 

우선 0이 있다는 것은 +도 되고, -도 되므로 그냥 0이 n개 있으면, 0을 빼고 결과값에 2^n 만큼 곱해주며 된다.

아무튼 다른 숫자들은 2차원 배열을 만들어서 dp에 넣으면 된다.

dp[가능한 숫자][현재까지 수행 횟수] 이런 식으로 하면, 최종적으로 원하는 숫자까지 가는데 만들 수 있는 등식의 수가 나온다.

항상 마지막에는 0의 개수만큼 2의 거듭제곱을 곱해주면 된다.

참고로 모든 숫자가 0일 때도 있어서, 그냥 try, except로 잡았다.

---

2.  코드

 

 

n = k = int(input()) - 1
maps = [m for m in map(int, input().split())]
try:
    ans = maps.pop()
    factor = 1 if maps[0] else 0.5      # 0이 있으면 그냥 빼고 2배수 해도 됨
    while 0 in maps:        # 0을 제거하고, factor를 2씩 곱함
        maps.remove(0)
        factor *= 2
        n -= 1
    dp = [[0] * n for _ in range(21)]     # dp[가능한 숫자][현재까지 수행 횟수]
    dp[maps[0]][0] = 1
    for i in range(1, n):       # 현재 수행 횟수
        for j in range(21):     # 가능한 숫자
            if temp := dp[j][i - 1]:
                if (cur := j - maps[i]) >= 0:
                    dp[cur][i] += dp[j][i - 1]
                if (cur := j + maps[i]) <= 20:
                    dp[cur][i] += dp[j][i - 1]
    print(dp[ans][n - 1] * int(factor))
except:     # 인자가 모두 0일때는 오류가 발생함
    print(2 ** (k - 1))

---

3.  마무리