[BOJ / 백준] 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 파이썬(Python) 문제 풀이

 

문제

 

문제 링크 : https://www.acmicpc.net/problem/2422

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

 

 

 

 

 

CODE

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
ice = [[False for _ in range(n)] for _ in range(n)]
for i in range(m):
    i1, i2 = map(int, input().split())
    ice[i1 - 1][i2 - 1] = True
    ice[i2 - 1][i1 - 1] = True

result = 0

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if not ice[i][j] and not ice[i][k] and not ice[j][k]:
                result += 1

print(result)

 

 

 

 

 

풀이

💡 idea 

- 각 아이스크림 종류 별로 섞어먹으면 안 되는 조합의 번호를 저장

- [브루트 포스] 모든 조합에 대해 섞어먹으면 안 되는 조합인지 검사한다

 

 

💡 implementation

- (초기) 조건문에 in을 사용한 경우 : 시간이 5배 이상 걸린다 🤦

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            if j not in ice[i] and k not in ice[i] and k not in ice[j]:
                result += 1

    ˙ ice에도 n번 아이스크림에 섞어먹으면 안 되는 조합의 번호를 리스트로 저장

    ˙ in 연산이 리스트 전체를 순회하기 때문에 시간이 오래 걸린다  →  ice를 boolean 값 가진 이중리스트로 수정

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if not ice[i][j] and not ice[i][k] and not ice[j][k]:
                result += 1

 

- 조합을 생성할 때, itertools의 combinations를 사용할 수도 있다

for i in combinations(range(n), 3):
    if ice[i[0]][i[1]] or ice[i[0]][i[2]] or ice[i[1]][i[2]]:
        continue
    result += 1

    ˙ 코드는 간편해지지만, 시간이 584ms로 조금 느려진다!

 

 

 

 

 

결과