본문 바로가기

PS2

[BOJ] 1450 : 냅색문제 문제 링크 1450번: 냅색문제 (acmicpc.net) 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 용량이 정해져있는 가방에 물건을 담을 수 있는 경우의 수를 구하는 냅색 문제이다. 예제1번을 예시로 보면 물건의 수는 2개, 가방의 최대 용량은 1 2개의 물건은 각각 무게가 1이다. 무게가 같더라도 두 물건은 다른 물건이다. 아무것도 담지않는 경우 1 + 첫번째 물건만 담는 경우 1 + 두번째 물건만 담는 경우 1 이렇게 해서 경우의 수는 3이다. 냅다 그냥 조합으로 경우의 수를 구하면 시간 초과다.. 2022. 2. 4.

[BOJ] 2470 : 두 용액 문제 링크 2470번: 두 용액 (acmicpc.net) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 두 용액의 특성값의 합이 0에 가장 가까운 용액을 만드는 문제. 브루트포스로 해결하려 한다면 O(N^2) 이기때문에 당연히 시간초과가 난다. 투포인트 기법을 사용해야하는데 말 그대로 그냥 두 개의 점을 찍는 방식이다. 먼저 용액의 특성값들이 담긴 벡터를 오름차순으로 정렬한다. Left를 0 Right를 N-1로 잡고(Left와 Right가 두 점이 된다) 벡터의 Le.. 2022. 2. 2.

이전 1 다음

티스토리툴바