[프로그래머스] Lv2 위장

개발하는 구황작물·2022년 11월 24일
0

알고리즘

목록 보기
3/8

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류이름
얼굴동그란 안경, 검정 선글라스
상의파란색 티셔츠
하의청바지
겉옷긴 코트

스파이가 가진 의상들이 담긴 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이다.

profile
어쩌다보니 개발하게 된 구황작물

0개의 댓글