20.05.19 - 2015 ACM-ICPC 연습

https://www.acmicpc.net/contest/view/116

2015 ACM-ICPC 연습

오늘은 저번에 풀다 만 Virus 문제를 풀고, Party 문제를 해석하였습니다.

 

Virus 문제에서 고민을 했던 순회, 고립 등의 문제는 발생하지 않았습니다.

조건 상으로도 발생하지 않기도 했지만, 애당초 그런 입력을 주지 않는 것 같습니다.

코드를 제출 한 결과 50% 부분에서 시간초과가 났습니다.

대부분 이 부분에서 문제가 생기는 것 같은데, 몇 가지 시도를 하다가 우선은 보류하였습니다.

Vector를 사용하는 것이 문제가 될거라 생각하지는 않습니다.

동적할당으로 바꾸면 문제 해결에 도움은 될것이지만, 근본적인 알고리즘이 문제일 것이라 생각합니다.

 

Party는 아싸 컴공 학생들을 간호과 학생과 미팅시켜주는 문제입니다.

컴공과 학생과 간호과 학생을 불러 파티를 개최합니다.

파티 후 간호과 학생들이 선호하는 컴공과 학생 중 한명과 데이트를 합니다.

이 때 최소 몇번의 파티를 개최하면 모든 컴공과 학생들이 최소 1번은 데이트를 하는지 구하는 문제입니다.

단, 파티를 아무리 해도 모든 학생이 데이트를 하는 것이 불가능 하다면 이를 따로 출력해야 합니다.

 

문제 푸는 방식을 구상하는 것은 다음 주에 할 예정입니다.