100일 동안 매일 알고리즘을 하면?

알고리즘

유병각 2021. 12. 31. 01:38

100일 동안 매일 알고리즘을 하면? - 5일차

모자가 3종류 , 안경이 2종류, 신발이 3종류라고 할때

(모자 3종류 + 모자를 안쓰는 경우) * (안경 2종류 + 안경를 안쓰는 경우) * (신발 3종류 + 신발를 안쓰는 경우)

= 4 * 3 * 4 - 1(아무것도 안입는 경우는 없으므로 1을 뺌)

이런식으로 간단한 경우의수 계산으로 풀 수있다.

처음에 이 문제를 어떻게 접근할지 고민하다가 combination (조합) 을 활용해서 풀었는데,

조합으로 풀면 시간 복잡도가 2^30 으로 너무 크게 나온다.

코딩테스트 연습 - 위장

programmers.co.kr