백준 5557 (1학년)

백준 5557 (1학년)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/5557

문제 접근

상근이는 아직 1학년이라서 0~20 사이의 정수만 알고 있다고 합니다. 아마 손가락 발가락으로 셀 수 있는 숫자의 범위로 추정됩니다. 총 N개의 숫자가 주어지는데, 이 숫자들 사이에 +, -를 적절하게 넣어 입력의 제일 마지막 숫자를 만들 수 있는 경우의 수를 구하는 문제입니다. n의 범위가 얼마 되지 않는다면 완전탐색으로 충분히 빠르게 정답을 구할 수 있지만, N<=100이므로 완전탐색을 하는 O(2^n)으로는 풀 수가 없음을 알 수가 있습니다.

하지만 처음부터 i번째 수까지 연산을 한 결과가, i+1번째에 영향을 준다는 사실을 알 수가 있습니다. 예시로 1~i번째 수까지 연산을 했는데, 8이 5번, 10이 7번 나왔다고 가정해봅시다. i+1번째 수는 2라고 가정해보도록 하겠습니다.

1~i+1번째 수까지 연산한 결과는 8에서 +2, -2한 경우와, 10에서 +2, -2한 경우로 나뉩니다.

1) 8이 5번 나왔습니다. 이를 토대로, 10이 나온 경우는 5번, 6이 나온 경우는 5번이 나옵니다. 2) 10이 7번 나왔습니다. 이를 토대로, 12가 나온 경우는 7번, 8이 나온 경우는 7번입니다.

따라서, i+1번째까지 연산한 결과는 6이 5번, 8이 7번, 10이 5번, 12가 7번 나옴을 알 수가 있습니다.

dp[i-1][k]는 1에서 i-1번째 수까지 연산한 결과의 값이 k일 때, 이때 경우의 수라고 하겠습니다. 현재 i번째 수를 number이라고 하겠습니다.

이를 점화식으로 적는다면 dp[i][k+number] = dp[i-1][k]으로 쓸 수가 있습니다. 물론 k+number은 0~20 사이 정수여야 합니다.

if j+number>=0 and j+number<=20 :
    dp[i][j+number]+=dp[i-1][j]
if j-number>=0 and j-number<=20 :
    dp[i][j-number]+=dp[i-1][j]

로 작성할 수 있습니다.

소스 코드

import sys

n=int(input())
seq=[0]+ list(map(int,sys.stdin.readline().split()))
target=seq[-1]
seq=seq[:-1]
dp=[[0]*21 for _ in range(n+1)]
dp[1][seq[1]]=1

for i in range(2,n) : 
    number=seq[i]
    for j in range(21) : #0~20
        if dp[i-1][j]!= 0 : #0인 경우는 1~i-1번째 수 까지 연산한 결과가 j인 경우의 수가 존재하지 않음.
            if j+number>=0 and j+number<=20 :
                dp[i][j+number]+=dp[i-1][j]
            if j-number>=0 and j-number<=20 :
                dp[i][j-number]+=dp[i-1][j]

print(dp[n-1][target])

마무리하며

간단한 dp문제였습니다. 오늘 일어났는데 속이 너무 아팠습니다.. 그래서 죽 하나 시켜먹었습니다.. 앞으로 먹고 바로 눕지 않아야겠습니다. .
카페에서 그린데이 노래를 들으면서 코딩이나 해야겠습니다..