A. Help Farmer$\!$
$A*B*C$의 값이 주어졌을 때, $(A + 1) * (B + 2) * (C + 2) - A * B * C$의 값의 최대, 최솟값을 구하는 문제이다.
$A*B*C$의 값은 상수이므로 $(A + 1) * (B + 2) * (C + 2)$를 결정해주면 되는데, $A*B*C$의 값 $n$의 약수를 모두 돌아보며 $A$, $B$의 값을 결정해주면 된다. ($A$, $B$가 결정되면 $C$는 알아서 결정되므로 고려할 필요가 없다.)
2중 for문 으로 해결되는데, 약수를 결정하고나면 그 반대 쌍도 $A$나 $B$값으로 고려하여 체크해봐야한다.(예제를 돌려보면 무슨 뜻인지 이해가 갈 것이다.)
문제는 이게 시간내에 돌아가느냐인데.. 약수결정에 O($sqrt(n)$)이 걸리고, 또 거기서 O($sqrt(n)$)이 걸리므로 O($sqrt(n)$ + $sqrt(sqrt(n))$)으로 O($sqrt(n)$)이 걸리니까 $(10^9)^{1/2}$ = 31,622 잘 돌아간다.
처음엔 안 돌아갈줄 알고 $A$를 결정하고 parametric을 써야하나.. 싶었는데 결정함수 설계가 불가능한것 같아서 설마하고 naive하게 돌려보니 통과.
체스판에 나이트를 하나 놓으면, 나이트가 1번에 움직일 수 있는 위치에는 다른 나이트를 놓을 수가 없다. 이때 나이트를 최대한 놓는 문제이다.
일단 가장 간단한 풀이는 greedy이다. tourist의 코드를 보고 이해가 안 되서 답지를 보니 이런 코드가 나온다. 먼저, 일반적인 해는 $(n * m + 1) / 2$ 이다.
하지만 예외가 있다. 1줄짜리 이거나 2줄짜리인 경우. 코포 솔루션에서 언급했듯이 이 예외 찾기가 상당히 어려운데 그래서 hack이 많단다. 당장 상위랭커들 log보면 hack이 10개씩 된다.
1칸짜리 예외는 찾기가 쉽다. 문제는 2칸이 포함될 경우의 예외인데, 편의상 2줄인 줄을 n, 다른 줄을 m이라 하자. m방향으로 4줄마다 그 중 왼쪽으로 2줄을 채울 수 있다는 것은 바로 눈에 보인다. 즉 8칸마다 왼쪽으로 쫙 붙혀서 4칸을 채울 수 있다. 문제는 m을 4줄 단위로 자른 뒤 남은 줄인데, 0줄이 남은경우는 0, 1줄이 남은경우는 1, 2줄이 남은경우는 2, 3줄도 2줄을 채울수 있다. 그래서 $min(m % 4, 2) * 2$가 되는 것이다.
일반적인 해는 그냥 대각선으로 쭈욱 채우면 된다.
딱 보자마자 이거 네트워크 같은데.. 싶어서 네트워크로 접근했는데 다른사람들 코드를 보니 네트워크로 푼 사람이 꽤 된다.
형태보니 이분매칭해줘야 될것같아서 그래프 모델링을 어떻게 해야하나.. 막 생각하다보니 어? 이거 greedy하게 답이 나오는데? 싶어서 greedy인갑다 싶어서 제출하니 틀림.. 둘 중 하나만 놓고 생각했으면 풀었을텐데 이거 greedy냐 네트워크냐 막 햇갈려서 이것저것 생각하다보니 엉켜버려서 손을 못 댓다. 결과는 둘 다 써도 되는 문제여서 더 화났다.
한가지 더 문제는 도대체 어떻게 그래프 모델링을 해야하는지 모르겠다. 시간 날 때 다시한번 생각해봐야겠다.
