[백준][Python] 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

브루트포스 / 실버 4

🍦

https://www.acmicpc.net/problem/2422

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

 

 

내 풀이

from itertools import combinations

N, M = map(int, input().split())
do_not_mix = [[] for _ in range(N+1)]
icecream = [x for x in range(1, N+1)]
three_icecream = []
ans = 0

for i in combinations(icecream, 3):
    three_icecream.append(list(i))

for _ in range(M):
    i1, i2 = map(int, input().split())
    do_not_mix[i1].append(i2)
    do_not_mix[i2].append(i1)

for i in range(len(three_icecream)):
    if three_icecream[i][1] in do_not_mix[three_icecream[i][0]] or three_icecream[i][2] in do_not_mix[three_icecream[i][0]] or three_icecream[i][1] in do_not_mix[three_icecream[i][2]]:
        continue
    ans += 1

print(ans)

 

 

코드 설명

 

조합(combination)으로 풀었다.

 

do_not_mix: 섞어먹으면 안 되는 조합의 번호를 저장하는 이차원 리스트. 인덱스 사용의 편리함을 위해 N+1 크기로 선언. 0번 리스트는 쓰지 않고 비워둔다.

icecream: 아이스크림의 번호

three_icecream: 아이스크림 3개의 조합이 저장되는 이차원 리스트

 

섞어먹으면 안 되는 아이스크림의 번호를 입력받아, 각 리스트에 상대 번호를 추가한다.

for _ in range(M):
    i1, i2 = map(int, input().split())
    do_not_mix[i1].append(i2)
    do_not_mix[i2].append(i1)

 

가능한 모든 조합을 돌면서, 섞어먹으면 안 되는 아이스크림이 한 조합에 존재하는지 검사한다.

 

1. 첫 번째 아이스크림과 두 번째 아이스크림을 함께 조합하면 안 되는 경우

2. 첫 번째 아이스크림과 세 번째 아이스크림을 함께 조합하면 안 되는 경우

3. 두 번째 아이스크림과 세 번째 아이스크림을 함께 조합하면 안 되는 경우

 

순서가 바뀌어도 같은 경우로 간주하므로, 다음 세 가지의 경우만 검사하면 된다.

for i in range(len(three_icecream)):
    if three_icecream[i][1] in do_not_mix[three_icecream[i][0]] or three_icecream[i][2] in do_not_mix[three_icecream[i][0]] or three_icecream[i][1] in do_not_mix[three_icecream[i][2]]:
        continue
    ans += 1

 

 

 

어려웠던 점

 

처음에는 다음과 같이 코드를 짰었는데, 시간 초과가 발생했다.

이중 for문을 없애주니 해결되었다.

for i in range(len(do_not_mix)):
    for j in range(len(three_icecream)):
        if do_not_mix[i][0] not in three_icecream[j] and do_not_mix[i][1] not in three_icecream[j]:
            ans += 1