9명의 난쟁이들의 키가 주어지는데, 이 중 키의 합이 100이 되는 일곱 난쟁이를 알아내야 합니다.
이 때 난쟁이의 키를 오름차순으로 출력해야 합니다.
난쟁이의 수가 9명으로, input의 크기가 매우 작습니다.
7명을 선택하는 모든 경우의 수를 탐색할 수 있을지 생각 해봅시다.
🍯 TIP ! 이렇게 모든 경우를 탐색하는 것을 완전 탐색이라고 부르며, 완전탐색은 보통 input의 크기가 작을 때 사용 할 수 있습니다.)
여기서 약간의 아이디어를 떠올리면 좋은데요,
9명의 난쟁이 중 7명을 선택한다는 것은 반대로 말하면 9명의 난쟁이 중 제외할 2명의 난쟁이를 선택하는 것과 같습니다.
7명을 선택하는 모든 경우의 수를 만드는 코드를 구현하는 것 보다, 2명을 선택하는 모든 경우의 수를 만드는 코드를 구현하는 것이 훨씬 쉽겠죠?
이렇게 코드 구현 편의성을 위해 아이디어가 조금 필요한 경우가 있습니다.
자 그럼 경우의 수가 얼마나 될지, 시간안에 연산이 가능할지 검토해보겠습니다.
9명의 난쟁이 중 2명의 난쟁이를 선택하는 모든 경우의 수는 9 * 8로, 총 72가지입니다.
한 가지 경우에 대해 정답인지 판단하기 위해서는 난쟁이의 키의 합을 구하는 단순 연산만 필요합니다.
따라서 2초의 시간 제한안에 아주 넉넉하게 완전 탐색이 가능합니다.
🍯 TIP ! 코딩테스트에서는 1억번의 연산이 대략 1초 정도 걸린다고 생각하면 쉽습니다. (ex) 시간제한이 2초라면 2억번의 연산안에 풀이가 가능한지 체크해봅시다.