본문 바로가기

백준 #1450 #냅색문제 #두 포인터 #중간에서 만나기1

[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.

이전 1 다음

티스토리툴바