20.06.09 - 2015 ACM-ICPC 연습

https://redchiken.tistory.com/136

20.05.26 - 2015 ACM-ICPC 연습

풀수 있는 문제는 다 풀었고 이 뒤로는 넘기려고 합니다.

 

해결법은 예측이 가는데 너무 오래 잡으니까 도저히 손이 가지를 않습니다.

 

앞으로는 이런 하나의 문제 세트를 풀 때는 한달 단위로 시간을 제한해야 할 것 같습니다.

 

못풀었던 문제 중 Party는 아직 마땅한 해결법을 찾지 못했습니다.

Dynamic Programming을 쓰면 어떻게 될 것 같은데 구조를 명확히 떠올리지 못했습니다.

 

Save the computer는 Dynamic Programming을 쓸 것도 없이, 반복적인 계산으로 해결이 될 것 같습니다.

다만 이 계산을 유추해내는 과정이 수학적으로 복잡한 연산을 취해줘야 합니다.

 

Scorched Earth는 일반적인 식 하나로는 유추가 되지를 않았습니다.

풍속이 없는 경우, 동일 고도에 있는 경우, 동일 위도에 있는 경우 등에 대해 모두 경우를 나누어서 생각해야 합니다.

그 결과 적절한 식을 구하기는 했으나, 이를 프로그래밍까지 할 기운이 남지 않았습니다.

 

Free Willy는 연습 문제 중 가장 어려운 문제였던 것 같습니다.

전형적인 Branch and Bound로, 제한 횟수보다 1 낮을 때에만 연산이 줄어드는 경우라 생각합니다.

이대로 구현을 한다면 정답은 구하겠지만, 제한 시간 내에 풀지는 의문입니다.

 

다음주에는 DP를 문제를 2개 정도 풀어보려 합니다.

문제는 역시 backjoon 사이트에서 구해올 것 같습니다.