728x90
풀이
최대 200개의 아이스크림 중 3개로 이루어질 수 있는 조합의 개수만 세면 된다.
N의 최대값이 작으므로 주어지는 입력을 그래프로 구현 후 모든 경우를 다 살펴보자.
- ban_list [n1] [n2] : (n1, n2) 조합의 불가능 여부
- 단, 섞어먹으면 안되는 조합이 항상 오른차순으로 주어진다는 보장이 없어 양방향 그래프로 구현하자.
- 3개의 조합을 선별해야 하므로 순서는 상관없다.
또한, 양방향 그래프이기 때문에 그리디 로직(먼저 고른 수는 나중에 고른 수보다 항상 작음)을 적용시킬 수 있다.
조건을 모두 만족 (조합이 성립)하는 경우에만 아이스크림 조합의 수를 증가시켜 주자.
소스코드
출처
2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번
www.acmicpc.net
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 1389] 케빈 베이컨의 6단계 법칙 [Python] (0) | 2023.04.08 |
|---|---|
| [백준 27213] Граничные клетки [Python] (0) | 2023.04.07 |
| [백준 27239] Шахматная доска [Python] (0) | 2023.04.05 |
| [백준 27245] Комната [Python] (0) | 2023.04.04 |
| [백준 27880] Gahui and Soongsil University station [Python] (0) | 2023.04.03 |