[프로그래머스] 의상 파이썬

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

내 답안

from collections import defaultdict

def solution(clothes):
    dic = defaultdict(int)
    answer = 1
    for _, y in clothes:
        dic[y] += 1
            
    for _, j in dic.items():
        answer *= (j+1)
    
    return answer-1

---

Review

이 문제는 보자마자 구현이 아닌 수학적으로 접근해야겠다 생각했고,
처음에는 순열과 조합으로 생각했던 문제였습니다.

하지만 쉽게 도출하지 못했고 노트에 적어서 규칙성을 적은 결과 아래와 같이 생각할 수 있었습니다.
여기서 의상의 이름은 필요 없고, 의상의 종류가 필요했습니다.

입출력 예 1로 설명할게요
여기서 "headgear"를 1로 두고, "eyewear"를 2로 두면
아래와 같은 사진으로 정리할 수 있습니다.

각각 하나씩 입는경우 + 종류별 안겹치게 입는 경우 

를 계산해 준다면 결과를 도출 할 수 있습니다.

따라서 의상이 두가지인 경우 

∴ (N+1)(M+1) - 1

이라는 식으로 결과를 도출 할 수 있고
4가지인 경우에는 아래와 같이 도출 할 수 있습니다.