[Programmers] 위장

Link: Lv2. Programmers – 위장

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

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

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

문제를 보자마자 느껴진 것이 우선 <옷의 종류, 옷의 개수>로 정리를 해야겠다는 생각이 들었다.

따라서 HashMap에 위와 같이 정리를 하고 마무리를 하려는데 생각보다 쉽지 않았다.

처음 떠오른 생각은 Dynamic Programming 을 이용한 방법이었다.

(a, b, c = 옷의 종류)

이런 식으로 곱해나가면서 저장하면 전체 경우의 수를 구할 수 있을 줄 알았다.

하지만 4 종류가 생기면 아래와 같이 두 개의 경우가 더 생겨서 불가능했다. (실패)

두 번째 방법은 나올 수 있는 경우의 수를 전체 구하는 방법이다.

S = { a, b, c, d} 라 하면 공집합을 포함하여 부분집합의 경우의 수는

2^n (2의 n 제곱) 이므로 16가지이다.

문제는 각각의 경우를 모두 다 구해서 더해야 하므로 효율이 안 좋을 것은 뻔했다. (실패)

(참고로 (nC0 + nC1 … nCn) 의 합은 2^n 으로 부분 집합의 합과 같다.)

세번째 방법은 옷 종류 마다 안 입는 경우를 +1 하여 전부 곱하는 방법이다.

그래, 이거였다. 그러면 옷 종류마다 자연스럽게 옷을 안 입는 경우의 수가 생긴다.

이렇게 했을 때 시간 복잡도는 BigO(n) 이다. (n = 옷의 가지 수)

Source Code: camouflage.cpp

Post Views: 7,234