[파이썬 | BOJ | 5557] 1학년

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

5557번: 1학년

문제

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 2^(63-1) 이하이다.

풀이

알고리즘 분류 : 다이나믹 프로그래밍

위 문제는 작은 문제로 쪼개서 풀 수 있는 것이 자명하므로 다이나믹 프로그래밍으로 해결 할 수 있다.

 

일단 예시로 주어진 수열에서 처음 3개의 수열부터 살펴보면서 규칙을 살펴본다.

일단 8을 이용해서 만들 수 있는 수는 8밖에 없다.

그 다음 8, 3을 이용해서 만들 수 있는 수는 5, 11이다.

그 다음 8, 3, 2를 이용해서 만들 수 있는 수는 3, 7, 9, 13이다

그 다음 8, 3, 2, 4를 이용해서 만들 수 있는 수는 7, 3, 11, 5, 13, 9, 17이다.

위 규칙을 보면서, 이차원 배열 D[index][0부터 20까지 가능한 수]를 구상 할 수 있다.

즉 D[1][8] = 1이고 나머지는 모두 0이라고 할 수 있다.(숫자 8을 이용해서 만들 수 있는 값은 8밖에 없다.)

D[2][5]=1, D[2][11]=1이고 나머지는 모두 0이다.

 

즉 위의 규칙대로 점화식을 세워보면 

D[index + 1][index 단계에서 가능한 수 + index단계에 주어진 수열] = D[index][index 단계에서 가능한 수]

D[index + 1][index 단계에서 가능한 수 - index단계에 주어진 수열] = D[index][index 단계에서 가능한 수]

 

라고 할 수 있다.

위 예시에 대입해보면

 

D[1+1][8-3] = D[1][8] = 1

D[1+1][8+3] = D[1][11] = 1 

이 되는 것이다.

 

따라서 반복문으로 D를 구성하면 다음과 같이 알고리즘을 구성할 수 있다.

# [파이썬 | BOJ | 5557] 1학년
import sys
read = sys.stdin.readline
 
N = int(read())
arr = list(map(int, read().split()))
D = [[0 for _ in range(21)] for _ in range(N+1)]
 
D[1][arr[0]] = 1
 
for j in range(1, N):
    for i in range(21):
        if D[j][i] > 0:
            if 0 <= i-arr[j] <= 20:
                D[j+1][i-arr[j]] += (D[j][i])
 
            if 0 <= i+arr[j] <= 20:
                D[j+1][i+arr[j]] += (D[j][i])
 
print(D[N-1][arr[N-1]])