백준온라인 16287번 [Parcel] [C++]

 

www.acmicpc.net/problem/16287

16287번: Parcel

 

---

문제요약

1.서로다른 N개의 정수가 주어졌을때 (4<=N <=5000)

2.4개를 선택하여 W를 만드는게 가능한지 안한지 판별하라

 

---

나의 풀이

4개를 구성하는 모든 경우를 보게 된다면 총 \(nC4\) 만큼의 경우의 수를 확인 해가면서 봐야한다

==> 시간초과

 

이 문제의 발상은 

4개를 구성하는 다른 가짓수 중에서 합이 W가 되는 경우를 찾는 문제를

 

합이 W가 되는 경우중 W를 구성하는 4개의 가짓수가 서로 다른가짓수인지 확인하는 문제로 바꿔서 생각할수 있다.

 

 

두 소포의 무게 합이 S이라 하면

W-S 만큼의 무게도 나머지 소포중 두개의 소포로 만들수 있어야 한다 

 

이러한 과정들이 다음과 같은 논리를 가진다

(첫번째 + 두번째 ) + (세번째 , 네번째 ) = W를 만족하는 경우

첫번째 != 두번째 != 세번째 != 네번째 가 되어야 한다

 

우선 두개의 소포를 선택하여 만들수 있는 조합을 임의의 무게 S에 대하여 저장해놓는다

 시간복잡도 : \(O(N^2)\)

 

세번쨰 , 네번째 조합으로 만드는 무게V에 대하여 W-V로 만드는 경우가 있는지?

있다면  첫번째 != 두번째 != 세번째 != 네번째 를 만족하는지 판별해주면 된다.

시간복잡도 : \(O(N^2)\)

---

코드