[PS] BOJ 26596 / 황금 칵테일

Minjun Kim

15 May 2025 • 1 min read

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

Thumbnail: Photo by Nuff . (Unsplash)

황금 칵테일 한잔, 온더락으로.

풀이

\(M\)회에 걸쳐 재료들을 투입하게 되는데, 이중에는 같은 재료가 여러 번 들어갈 수도 있습니다. 따라서, 각 재료마다 투입된 총량을 계산할 필요가 있는데, 저는 Map 자료구조의 일종인 딕셔너리(dict)를 사용해 구현했습니다.

재료별 총량을 계산한 뒤로, 들어간 재료의 종류가 \(N\)개라 하면 단순히 배열을 이중으로 모든 재료의 곱을 구하는 방식(\(O(N^2)\)) 으로 풀어도 시간제한 안에 풀 수 있습니다. 애당초 \(1 \le M \le 5000\) 이고 \(N \le M\) 이기 때문입니다.

하지만, 반복을 조금이라도 더 줄이자면 각 재료의 총량을 양을 기준으로 정렬해버린 뒤, 자기보다 큰 수와의 곱만 비교하게끔 반복을 줄일 수 있습니다.

전체 코드

input = open(0).readline
M = int(input())

ingredients = {}
for _ in range(M):
    ingredient, amount = input().rstrip().split()
    try:
        ingredients[ingredient] += int(amount)
    except KeyError:
        ingredients[ingredient] = int(amount)

amounts = sorted(ingredients.values())
result = False
for i in range(len(amounts) - 1):
    for j in range(i + 1, len(amounts)):
        if amounts[i] * 1618 // 1000 == amounts[j]:
            result = True
            break

print("Delicious!" if result else "Not Delicious...")

solution.py