[백준/5557/파이썬] 1학년

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

5557번: 1학년

Problem

• 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다.
• 상근이는 올바른 등식을 만들려고 한다. 숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

조건

• 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다.
• 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다.
• 첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

SOL

완전탐색으로 푼다면, +하는 경우,-하는 경우, 한 계산당 2가지의 경우의 수가 생기기 때문에, 2^n꼴이된다.

따라서, DP로 풀어야하고, DP스럽게 생겼다.

 

DP

 

"20을 넘는 수는 모른다"라는 조건 덕분에, DP로 쉽게 접근이 가능한 문제이다.

연산과정 중에서도, 20이 넘으면 안된다는 조건 덕분에, 모든 정수에 대한 DP table을 안만들어도 된다.

(애초에, 모든 정수에 대해서 table을 선언하는것도 불가능한 일이다)

 

신경써야할 것

• 경우의 수를 구하는 문제이기 때문에, 누적합을 구해줘야한다.
• 마지막 값은 target 값이 되기 때문에, 반복을 1개 덜 해줘야한다.
• 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다.

DP table

정의: DP[i][j] : i번째까지, j가 되는 경우의 수

초기값: DP[0][arr[0]] =1

점화식 : DP[i][j+arr[i]] += DP[i-1][j] , DP[i][j-arr[i]] += DP[i-1][j]

#DP
#bottom up
import sys
input = sys.stdin.readline
N = int(input().rstrip())
arr=list(map(int,input().split()))
DP = [[0]*21 for _ in range(N)]
DP[0][arr[0]] =1
target =arr[N-1]

# N-1 번째 숫자는 나와야하는 결과, (등호) 이므로, N-2까지만 반복

for i in range(1,N-1):
    for j in range(21):
        if DP[i-1][j] :
            if j+arr[i] <=20:
                DP[i][j+arr[i]] +=DP[i-1][j]
            if j-arr[i]>=0:
                DP[i][j-arr[i]] +=DP[i-1][j]

#for d in DP:
    #print(d)
#print(DP)
print(DP[N-2][target])