최근에 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' 카테고리의 다른 글

Ellipse (타원)  (0) 2009.04.15
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
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
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

to Top