반응형
https://www.acmicpc.net/problem/16287
16287번: Parcel
입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가
www.acmicpc.net
[ 문제풀이 ]
모든 경우의 수를 체크하기에는 $O(N^{4})$이라는 너무 많은 시간이 걸리므로 이를 반으로 쪼개 $O(N^{2} + N^{2})$의 시간 복잡도로 문제를 풀었습니다.
두 물건의 무게를 인덱스 값으로 하고, dp배열에는 각 물건의 인덱스 값을 저장합니다.
dp[ weight ] = i
dp2[ weight ] = j
이때 각 물품의 무게는 모두 다르므로 특정한 weight를 만족하는 쌍은 무슨 일이 있어도 겹치지 않으므로 한 쌍만 저장해주면 됩니다.
그리고 다시 한번 $O(N^{2})$의 시간 복잡도로 모든 쌍을 검사하면서 인덱스가 겹치지 않는 쌍이 있다면 YES를 출력해주고, 그렇지 않다면 NO를 출력해주면 됩니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<iostream> using namespace std; int w, n; int arr[5000]; int dp[400001]; int dp2[400001]; int main() { scanf("%d %d", &w, &n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int weight = arr[i] + arr[j]; //먼저 2개씩 더한 값들을 dp에 idx와 함께 저장 if (dp[weight] == 0) { dp[weight] = i; dp2[weight] = j; } } } for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { int weight = w - arr[i] - arr[j]; if (weight > 400000 || weight < 0) continue; //불가능한 경우 if (dp[weight] == i || dp2[weight] == j || dp[weight] == j || dp2[weight] == i || dp[weight] == 0) continue; //idx가 겹치는 경우 printf("YES"); //위의 조건이 아니라면 YES 출력 return 0; } } printf("NO"); //불가능하다면 NO 출력 } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 13141번 - Ignition (C++) (0) | 2022.08.08 |
|---|---|
| [ 백준 ] 7578번 - 공장 (C++) (0) | 2022.08.07 |
| [ 백준 ] 10026번 - 적록색약 (C++) (0) | 2022.08.05 |
| [ 백준 ] 11438번 - LCA 2 (C++) (0) | 2022.08.04 |
| [ 백준 ] 1725번 - 히스토그램 (C++) (0) | 2022.08.03 |