[백준] 11052번 - 카드 구매하기
1. 문제 이해 입력으로 N과 Pi가 P1부터 PN 까지 순서대로 주어진다. P의 인덱스를 i라고 하면, i의 합이 N이 되는 Pi들의 최댓값을 구하는 문제이다. 즉, 집합 P에 대한 중복조합이다. 부분집합의 합으로 정답을 구할 수 있지만 N의 최댓값이 10000이기 때문에 시간초과에 걸린다. 그래서 DP를 이용해서 풀어야 한다. 2. 문제 풀이 카드팩(N)은 N개의 카드가 들어있다. 카드팩(i)의 가격은 P(i)이다. N=4이고, Pi 가 순서대로 1 1 2 3 이 주어졌다면, 다음과 같이 풀 수 있다. N = 4 , P = { 1, 1 ,2 ,3} 카드팩 1개 구매 카드팩 1개를 구매하는 경우는 1가지이므로 P1, 즉 1이다. 카드팩 2개 구매 이 경우는 2가지 이다. P1 2개 혹은 P2 1개이다...
Algorithm Problem/백준
2022. 1. 26.