Jin의 일상

import sys
from itertools import combinations
# sys.stdin = open('input.txt', 'r')

INPUT = sys.stdin.readline


def solution():
    # 카드 세 장의 합(x)이 가장 큰 값을 리턴한다. (조건: x <= m)

    num_cards, m = map(int, INPUT().split())
    cards = map(int, INPUT().split())

    sum_3_each_cards = (a + b + c for a, b, c in combinations(cards, 3))

    res = -1
    for x in sum_3_each_cards:
        if x == m:
            return x
        if x > m:
            continue
        res = max(res, x)
    return res


if __name__ == '__main__':
    print(solution())

programmers.co.kr/learn/courses/30/lessons/42578

문제설명

1. 리스트에 1개 이상의 [의상의 이름, 의상의 종류]이 주어집니다.

ex) [[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]

2. 최소 한 개 이상의 옷을 착용 한다고 했을 때, 착용 가능한 옷의 조합 수를 구해야 합니다.

 - 동일한 종류의 의상은 착용이 불가능합니다.

ex) 위의 예시에서 yellow_hat과 green_turban은 동시착용이 불가능합니다.

문제 풀이

1. 다음과 같은 테스트 케이스가 주어졌다고 가정합니다.

2. 입력받은 데이터는 딕셔너리로 표현될 수 있습니다. 

3. 착용할 수 있는 의상을 종류에 따라 트리로 정리하면 아래와 같습니다.

- 의상 종류별로 입을 수 있는 경우의 수는 "총 개수 + 1" 입니다.

  - 예를 들어, headgear에 관한 경우의 수는 "yellow_hat", "green_turban", "착용X"이 있습니다.

따라서 모든 종류의 의상을 착용하지 않는 경우의 수를 제외하면

(headergear의 개수+1) * (eyewear의 개수+1) -1이 정답으로 출력 됩니다.

코드

def solution(clothes):
    types = {}
    for v, k in clothes:
        types[k] = types.get(k, 0) + 1

    cnt = 1
    for _, v in types.items():
        cnt *= v+1
    return cnt-1