(Python/🥈4)백준 알고리즘 2422번:한윤정이 이탈리아에 가서 아이스크림을 사먹는데

 

문제 바로가기 

한윤정 ~

 

문제:

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

입력:

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

출력:

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

 

풀이:

 

맞는거 같지만 시간초과로 틀린풀이

 

import sys
from itertools import combinations

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, M = map(int,input().split(" "))

lst = [list(map(int,sys.stdin.readline().rstrip().split(" "))) for _ in range(M)]
number = [i for i in range(1,N+1)]

num_lst = list(combinations(number,3))
res = []
for i in num_lst: # 조합을 하나 꺼내고 2 4 5
    for j in lst: # 만나면 안되는 리스트들을 하나씩 검사한다.
        flag = True
        jj = set(j)
        if len(set(i) & jj) == 2: # 조합이 성공되면
            flag = False
            break
    if flag == True:
        res.append(i)
print(res)

브루트포스 알고리즘 이라서 그냥 모든 조합 다 구했는데 틀리다

 

import sys
from itertools import combinations
N, M = map(int,input().split(" "))
# 그래프를 만들어 각 번호별 만나면 안되느 숫자들 True 로 바꿔줌.
graph = [[False] * N for _ in range(N)]
for i in range(M):
    a,b = map(int,sys.stdin.readline().rstrip().split(" "))
    graph[a-1][b-1] = True
    graph[b-1][a-1] = True

res = 0
for combi in combinations(range(N),3):

    if graph[combi[0]][combi[1]] or graph[combi[0]][combi[2]] or graph[combi[1]][combi[2]]: # 한 개라도 조합에 포함되어 있으면
        continue # 안됨
    res += 1 # 다 통과 했으면 되는거임
print(res)

그래프로 풀어주었다.

 

graph 에는 graph[고른숫자][다른숫자] 두 숫자가 조합을 이루면 안되는 숫자이면 True로 바꿔주면 된다.