(백준/ C++) 1450 - 냅색문제, 이분 탐색 완전 탐색 그려보자!

https://www.acmicpc.net/problem/1450

1450번: 냅색문제

 

이분 탐색은 생각하기 너무 어려운 문제인거 같습니다.

냅색이라는 이름만 보고 DP로 접근하려고 했는데 생각이 멈춰버렸습니다.... 언제 문제를 읽자마자 무슨 알고리즘을 써야하는지 떠오를까 ..ㅜㅜ

이 문제는 https://allmymight.tistory.com/99

[백준]1450번 냅색문제 - C++

이 분의 블로그를 참조하여 풀었으며, 여기서는 문제에 나오는 이분 탐색을 이해 해보는거에 집중을 했습니다.

일단 문제를 풀기 전에 1450 - 냅색문제에서 원하는 결과가 무엇인지 정확하게 알아봅시다.

문제는 N개의 물건을 가방에 넣는 방법의 수이다 예제 입력을 보면 0(아무것도 넣지 않았을 때 ) 또한 포함이 됩니다.

그럼 순열과 조합으로 생각했을 때 이 문제는 무엇일까요 ? 서로 다른 물건 중에서 한개를 뽑기도 하고 두개를 뽑기도 하고 세개를 뽑기도 하겠죠 ? 그 수의 합 중에 넣은 수있는 무게 보다 적어야하니까요.

서로 다른 N개에서 순서를 생각하지 않고 R개를 택하는 것. - (조합)
서로 다른 N개에서 R개를 택하여 일렬로 나열하는 것 - (순열) 

순서가 중요하지 않으니 조합이 맞을거 같습니다. 배열이 Arr[5]라고하면 순서를 생각하지 않고 ( 4개중에 4개 뽑는 경우의 수 + 4개중에 3개 뽑는 경우의 수 +  4개중에 2개 뽑는 경우의 수 +  4개중에 1개 뽑는 경우의 수 +  4개중에 0 개 뽑는 경우의 수) 를 모두 구해서 정렬해서 가방에 무게와 같거나 작은 개수를 확인하면 됩니다.

$${_4}C_0 + {_4}C_1 + {_4}C_2 +{_4}C_3 + {_4}C_4 = 1 + 4 + 6 + 4 + 1 =  16 $$ 

어떻게 흘러가는지 그림을 그리지 않으면 이해하기 어려워서 노가다로 코드 그림을 그려보았습니다. 저에게만 이해갈지는 모르겠지만 .. 이 그림은 N이 8일때를 기준으로 한 그림이고 0, 1, 2, 3, 4 까지의 합을 구하는 코드의 흐름 중 일부입니다.

배열은 arr[8] =  {1, 1, 1, 1, 1, 1, 1, 1}을 기준으로 작성한 예시입니다.

한번쯤은 직접 손으로 그려보고 코드의 흐름을 보면 좋을거 같습니다.  아래를 참고하세요. 긴 여정이 될겁니다.

 

 

참고한 블로그와 코드가 비슷하여 문제 풀이 코드는 넣지 않았습니다.

그럼 .. 안녕히 ..