[BOJ] Q5557 1학년

[BOJ] Q5557 1학년

Question

Language: Python

Difficulty: Gold 5

주어진 숫자 조합을 이용해서 +,- 의 기호를 포함시켜 만들어 낼 수 있는 등식의 개수를 구하는 문제이다. 해당 문제는 중간중간 나올 수 있는 중간 연산 결과를 DP로 저장해놓음으로써 등식의 개수를 구해낼수 있다.

예를 들어 예제 1번의 숫자는 아래와 같다.

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

1번째 숫자까지 봤을 때 나올 수 있는 연산의 종류는: 8 / 1개이다. 2번째 숫자까지 봤을 때 나올 수 있는 연산의 종류는: 8+3,8-3 / 2개이다. 이런식으로 각각 중간 연산결과로 나올 수 있는 등식의 개수를 저장해놓고 이를 다음 연산 시 참조한다.

Algorithm

for i in range(1,num):
  for j in range(0,21):
    #이전에 나올 수 있는 중간 결과인지 확인
    if dp[i-1][j]!=0:
      num=numbers[i]
      if j-num >=0:
        dp[i][j-num]+=dp[i-1][j]
      if j+num <21:
        dp[i][j+num]+=dp[i-1][j]

Solution

def solution():
    dp=[[0] * 21 for _ in range(num-1)]
    dp[0][numbers[0]]=1
  
    for i in range(1,num-1):
        for value in range(21):
            if dp[i-1][value]!=0:
                if value+numbers[i]<=20:
                    dp[i][value+numbers[i]]+=dp[i-1][value]
                if value-numbers[i]>=0:
                    dp[i][value-numbers[i]]+=dp[i-1][value]

    print(dp[-1][numbers[-1]])
  
if __name__ == "__main__":
    num=int(input())
    numbers=list(map(int,input().split()))
    solution()