Asia Regional - Daejeon 2015 모든 문제 풀이

문제집 : https://www.acmicpc.net/category/detail/1413

풀이는 하나하나 업데이트 될 예정입니다.

간략한 문제 분류와 솔루션만 제시 해놓고 풀이가 따로 필요하다고 생각되는 문제들은 추후 링크 하도록 하겠습니다. (요청하시면 그 부분에 관한 풀이도 올려드리겠습니다. ) 

A. Coin Swap  BOJ 11493

 flow문제 중에서도 MCMF문제다.  "동전의 교환 = 코스트" 로 두고 흰색을 모두 흰색으로 옮길때의 최소 코스트로 그래프 설계를 하면 된다.(검은색을 검은색으로 옮기는 코스트로 생각해도 무방) 흰색 정점이 있는 곳을 src와 연결하고 흰색 동전이 있는 곳을 sink로 돌렸을 때 나오는 MCMF결과를 출력하면 된다.

C. Grid BOJ 11495

 flow 문제 중에서도 이분 그래프로 만든 후 최대매칭하는 문제다. 익히 알려진 사실로 최대 매칭은 flow와 동치다.
 각각의 그리드를 순서대로 1, 2, 3,4... 번호를 매긴 후 인접한 것 끼리 연결한다. 이때 짝수는 src에 홀수는 sink에 연결하며 각각의 캐퍼시티는 그 그리드의 값으로 하고 매칭을 찾으면 된다.
 이 때 결과를 찾는 방법은 두가지 있는데 src와 sink에 남아 있는 캐퍼시티를 추적하는 방법과 전체에서 매칭의 수를 빼는 방법이 있다.(1매칭은 1코스트를 감소시켜주므로) 

D. Kernel  BOJ 11496

 기하 문제다.(segment tree로도 풀린다고 한다.) kernel이 존재할 수 있는 구간을 결정하고 그 위치가 주어진 polygon사이에 존재하는 지 결정하는 문제다. 열심히 그려보다보면 어떤 방식으로 kernel이 존재할 수 있는 구간을 결정하는 지 알 수 있다.(솔직히 이런걸 대회중에 발견하기는 어려워 보인다..)

E. Log Jumping BOJ 11497

 그리디 문제다. 통나무들을 길이 순으로 정렬하고 원의 왼쪽 오른쪽 차례대로 배치해 나가면 최적이 된다. 

F. Odd Cycle BOJ 11498

 그래프 문제 중에서도 SCC를 사용하여 시간을 줄이는 문제다. 사실 진짜 별거 없고 coloring하는데 그 coloring을 SCC내에서 하면 되는 문제다. 근데 한가지 조심해야할게 그냥 돌리면 WA가 날 수 있는데 사이클이 여러개 존재할 수 있다. 따라서 coloring을 back edge만 체크하게 해야한다. 이때 잘 처리 해줘야 TLE가 안난다. 

G. Path BOJ 11499

 기하 문제 중에서도 Convex_hull을 사용하는 문제다. 사실 그냥 컨백스 홀 만드는 방식으로 그냥 쭉 훑으면서 만들면서 최대 값을 갱신만 시켜주면된다.

H. Polynomial BOJ 11500 솔루션

 그냥 수식을 정리하는 문제다. 수학적 센스가 필요한 것 같다. (이미 알고 있다면 개꿀이었을 듯...) 수식을 정리해서 그대로 대입하면 된다. (하루종일 정리하면 된다.) 거듭 제곱의 합에 관하여 정리해야 한다.

I. Stock BOJ 11501

 파라매트릭 서치 문제다. 특정 상한을 결정하고 만들 수 있는지 검사한다. 이 때 검사는 선형으로 할 수 있어서 O(n) 그리고 파라매트릭에 logn이 들어 총 O(nlogn)이 든다. 

J. 3-Primes Problem BOJ 11502

 

 추측이라는데 그런가 보다 하면 된다. 그냥 하라는데로 하면 되는데 1000밖에 안된다. 따라서 소수 a,b를 결정하면 자동으로c가 결정된다. 여러가지 방법이 있는데, 전수 검사를 해서 (a,b,결정하고 c가 소수인지 확인) 푸는 방법, 넵섹하는 법, 등등 있다.

K. Tree Edit BOJ 11503

트리 dp문제다. 아직 안풀었다.

 L. Wheel of Numbers BOJ 11504

시뮬레이션 문제다. 직접 다해보면 된다.