[백준/Python] 5557 - 1학년

문제 링크

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

5557번: 1학년

 

문제 풀이

상근이가 왼쪽부터 숫자들을 더하거나 빼나가며 최우항의 숫자를 만드는 경우의 수를 출력하는 문제이다.

완전 탐색을 사용하면 단순하게 생각하였을 때 O(2^n)의 시간복잡도를 가지기 때문에 패턴을 찾아 문제를 풀어야 한다.

문제 설명 중 "상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다." 라는 힌트가 있다.

위 힌트를 이용하면 앞에서부터 숫자를 더해가며 경우의 수를 가지치기 할 수 있으며, 그 다음 수가 그것을 참조하여 문제를 풀어나가는 다이나믹 프로그래밍 기법으로 문제를 풀 수 있다.

예를 들면, 식이 "5 1 1 3" 으로 주어졌을 때 다음과 같은 과정으로 문제를 해결할 수 있다.

 

i-1번째 숫자의 계산 결과 후보에 i번째 숫자를 더하거나 빼어 답을 찾아나가면 된다. 그 때 사용되는 dp 테이블은 다음과 같이 정의된다.

 

dp[i][j] = i번째 숫자를 더하거나 뺐을 때 그 결과가 숫자 j가 되는 경우의 수

 

코드

n = int(input())
numbers = list(map(int,input().split()))
target = numbers[n-1]
numbers = numbers[:n-1]

# dp[i][j] = i번째 항에서 j를 만들 수 있는 경우의 수
dp = [[0 for _ in range(21)] for _ in range(n-1)]

dp[0][numbers[0]] = 1

for i in range(1, n-1):
    number = numbers[i]
    for j in range(21):
        if dp[i-1][j]:
            # j + number or j - number
            if 0 <= j + number <= 20:
                dp[i][j + number] += dp[i-1][j]
            if 0 <= j - number <= 20:
                dp[i][j - number] += dp[i-1][j]

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