[Programmers] 위장

 

문제

실수

대놓고 서로 다른 '조합'의 수를 구하는 문구에서

 

기계적으로 Combination을 떠올렸다.

옷의 갯수 까지의 모든 Combination 조합을 합하면 답이 도출되지 않을까? 하고 생각했다.

예를 들어 위의 예제대로 하면

얼굴(2) - 상의(1) - 하의(1) - 겉옷(1)

5C1 + 5C2 - 1(얼굴 2개만 뽑는 경우의수 ) + 5C3 - 3 (얼굴 2개  + 나머지 1조합 경우의수) + 5C4 - 3 (얼굴 2개 + 2개 조합 경우의수)

 

------ 이런 식으로하니 일반식이 도출되지 않았다.

 

 

아이디어

조합의 수를 구하라 했지만

옷을 하나이상 걸친 모든 경우의 수를 구하는 문제였다.

 

각 옷의 종류마다 옷을 입는 경우의 수를 나눠서 표현하면

 

얼굴 -> 입지 않음 , 동그란 안경 , 검정 선글라스 (3가지)

상의 -> 입지 않음, 파란 티셔츠 (2가지)

하의 -> 입지 않음, 청바지 (2가지)

겉옷 -> 입지 않음, 긴코트 (2가지)

 

※ "스파이는 하루에 최소 한 개의 의상은 입습니다" -> 모두 입지 않은 경우의수 1은 제외

∴ 최종 식 : 3 * 2 * 2 * 2 -1

∴ 일반식: (n + 1)(m + 1) … -1 // n, m : 옷 종류별 개수

풀이 (Kotlin)