서론
오늘은 SW Expert Academy에서 D3 문제를 골랐습니다. 정답률이 낮아서 좀 어려울 것 같습니다.
문제 분석
문제의 요구사항은 다음과 같습니다.
A1, A2, ... , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램을 작성하는 것입니다.
입력으로는 테스트 케이스의 수 T, 각 테스트 케이스의 N(1 ≤ N ≤ 20)과 K(1 ≤ K ≤ 1000), 그리고 N개의 자연수 수열 A가 주어집니다. 수열의 원소인 N개의 자연수는 1 이상 100 이하입니다.
계획 수립
처음에는 조합을 전부 해보는 방식으로 접근했습니다.
import sys
from itertools import combinations
sys.stdin = open("input.txt", "r")
T = int(input())
for test_case in range(1, T + 1):
N, K = map(int, input().split())
A = list(map(int, input().split()))
res = 0
for i in range(1, N):
sums = [sum(comb) for comb in list(combinations(A, i))]
res += sums.count(K)
print("#%d %d" % (test_case, res))
Python
복사
예상대로 시간 초과가 발생해서, DP로 풀어보기로 했습니다.
한참 쓰다가 다시 생각해보니, 좀 더 단순하게 DP를 적용할 수 있었습니다.
import sys
sys.stdin = open("input.txt", "r")
T = int(input())
for test_case in range(1, T + 1):
N, K = map(int, input().split())
A = list(map(int, input().split()))
# dp[i] : i를 만들 수 있는 수열의 수
dp = [0] * (K+1)
dp[0] = 1
for a in A:
for i in range(K, a-1, -1):
dp[i] += dp[i-a]
print("#%d %d" % (test_case, dp[K]))
Python
복사
회고
오늘의 학습 포인트는 DP 문제에서 상태를 정의하는 방법과 점화식을 세우는 방법입니다. 처음에는 복잡하게 생각했지만, 문제를 단순화하니 쉽게 풀 수 있었습니다. 앞으로는 DP 문제를 풀 때 상태 정의와 점화식에 더 집중해야겠습니다.
