백준 15824번 너 봄에는 캡사이신이 맛있단다 - 스위프트(Swift) 풀이
서브 태스크 문제로 small N과 large N 각각 점수가 매겨져 있어 small N만 통과해도 부분점수를 받을 수 있다. 먼저 small N에 맞게 풀이를 떠올리는 것은 쉽다. 결국 최소와 최대만 필요하므로 2개를 뽑아 그 2개가 (최소, 최대)가 되는 경우의 수를 각각 세서 곱해주면 된다. 이때 정렬을 하면 경우의 수를 쉽게 구할 수 있다. [1, 3, 4, 10, 11]이 있고 (3, 11)이 각각 최소, 최대가 되는 경우의 수를 구해보자. 3보다 크고 11보다 작은 숫자는 [4, 10]이 있으므로 이것들이 각각 있는 경우와 없는 경우를 고려하면 2^2가지이다. 모든 경우의 수를 나열하면 [3, 11], [3, 4, 11], [3, 10, 11], [3, 4, 10, 11]이 되겠다. 이렇게 풀..
2022. 1. 9.
백준 16287번 Parcel - 스위프트(Swift) 풀이 + 그림 설명
아이디어가 생각이 안 나서 결국 검색으로 해결한 문제ㅠㅠ DP라는 것은 감이 왔는데 지금까지 풀었던 DP 방식은 시간 초과 때문에 적용할 수가 없었다. 처음에 떠올렸던 방식은 dp(count, index, targetWeight) = weights[index...] 에서 count개의 소포를 뽑아 targetWeight를 딱 맞출 수 있는지 여부로 두고, index번째 item을 뽑는 경우 & 뽑지 않는 경우를 모두 고려하여 아래와 같은 식으로 푸는 것이었다. 하지만 count는 4, index는 5000, targetWeight는 무려 799,994여서 4*5000*799,994로 시간 안에 풀어낼 수가 없다.. dp(count, index, targetWeight) = dp(count - 1, ind..
2022. 1. 7.
