문제 설명
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
종류 | 이름 |
---|---|
얼굴 | 동그란 안경, 검정 선글라스 |
상의 | 파란색 티셔츠 |
하의 | 청바지 |
겉옷 | 긴 코트 |
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
먼저
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"]]
로 예시를 먼저 들어보겠다.
가짓수는
yellow_hat
blue_sunglasses
yellow_hat, blue_sunglasses
로 세가지를 들 수 있다.
이번에는
[[yellow_hat, headgear], [blue_sunglasses, eyewear], [black_sweater, upper_clothes]]
로 위의 경우보다 종류가 하나 더 는 상태로 예시를 들어보면
yellow_hat
blue_sunglasses
black_sweater
yellow_hat, blue_sunglasses
yellow_hat, black_sweater
blue_sunglasses, black_sweater
yellow_hat, blue_sunglasses, black_sweater
로 7가지를 들 수 있다.
위에서 규칙을 찾아보면
옷 종류가 2개이고 옷 개수가 각각 a, b 개일 때
옷을 한 개만 고르는 경우의 수 : a + b
옷을 두개 고르는 경우의 수 : ab
총 a + b + ab로 계산된다.
이번에 옷 종류를 a, b, c 3개로 한다면
옷 하나만 고르는 경우의 수 : a + b + c
옷 두개 고르는 경우의 수 : ab + bc + ca
옷 세개 고르는 경우의 수 : abc
총 a + b + c + ab + bc + ca + abc 개 이다.
중학교 수학 시간 때를 되돌아보면 어딘가 익숙하다고 생각 될 것이다.
바로 다항식의 계산인데
a + b + ab는 (1+a)(1+b) - 1와 같고
a + b + c + ab + bc + ca + abc 는 (1+a)(1+b)(1+c) - 1 와 같다.
즉, 이 문제의 답은 (1+a)(1+b)(1+c).... -1이다.