최근에 UVa 모의고사를 참여했는데.. 문제가 비교적 쉬워서 3문제를 풀고..
마지막으로 D번을 풀려고했는데.. 문제가 도저히 이해가 안되서.. 그냥 포기하고 잤다..

문제는 11414 - Dream 인데.. 그냥 까먹고 있다가..
최근에 10720 - Graph Construction 문제를 우연히 보고나서.. 이게 같은문제란걸 파악.. -_-;;

문제 description을 어떻게 저렇게 엉망으로 써놓을수가 있는지.. 참내.. 내가 영어를 못하는건가.. 흑.. ㅠ_ㅠ;

이 문제는 Erdos & Gallai Theorem으로 해결할 수 있는데..
vertex의 개수와 각 vertex의 degree가 주어지고.. 이를 만족하는 simple graph를 그릴수 있는지 묻는 문제..
여기서의 simple graph는 undirect이고 self edge가 없고 같은 pair의 vertex를 연결하는 edge는 최대 하나이어야 한다..


참고자료:




'Problem Solving > Algorithm notes' 카테고리의 다른 글

Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04
Game Theory  (0) 2007.12.19
Misère Nim  (2) 2007.12.16
BSP Tree  (0) 2007.08.28
Catalan Number  (10) 2007.08.12
Multinomial Theorem  (0) 2007.08.04

Leave a Comment


to Top