[백준] 2422번 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - python[ 조합 ]

[Silver IV] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 - 2422

문제 링크

성능 요약

메모리: 34044 KB, 시간: 1408 ms

분류

브루트포스 알고리즘

제출 일자

2024년 9월 30일 15:11:23

문제 설명

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

입력

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

출력

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

나의 풀이

조합 코드가 익숙하지 않아서 한참 걸렸다. nC3을 구현하고, 조건에 맞춰 거르는 문제였다고 생각한다.

지금보니 flag 안쓰고 for else문으로 가능해보인다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

count = 0
N,M = map(int, input().split())
lst = [[] for _ in range(N+1)]
sel = [0] * 3

for _ in range(M):
    a,b = map(int,input().split())
    lst[a].append(b)
    lst[b].append(a)

def combination(idx, sidx):
    global count

    if sidx == 3:
        count +=1
        return

    if idx == N:
        return

    flag = True
    for i in range(0, sidx):
        if sel[i] in lst[idx + 1]:
            flag = False
            break
    if flag:
        sel[sidx] = idx + 1
        combination(idx+1, sidx+1)
    combination(idx+1, sidx)

combination(0,0)
print(count)