9월 PS 일지

따로 글을 쓰기에는 애매한 문제들이 있고, 그래도 풀이를 간단하게라도 정리하는 것이 필요해서, 다른 사람들의 방식을 빌려서 정리하려고 한다. 보통 플레 수준의 문제. 이번에는 8월 달에 문 문제도 일부 포함되어 있다.

BOJ 7036 Grazing on the Run

풀이

DP 향이 강하게 난다. 특히 파일 합치기 느낌으로 dp[i][j] = i~j 의 구간관리. 

일단 첫번째로 구간 i~j 의 모든 건초를 먹었으면 위치 i또는 j에 있을 것이다. 따라서 [i][j][k] 에서 k로 최종적으로 i에 있는지 j에 있는지를 확인하자.

dp[i][j][k]에 어떻게 값을 저장할 지가 핵심이다. 구간을 다 먹었을 때 최소치만을 고려하면, 지금까지 걸린 시간에 따라서 앞으로 먹을 건초가 달라지기 때문에 최소치,시간 페어를 고려해야 한다. 
이는 사수아탕을 통해서 유명해진 테크닉으로 모든 건초의 부패량을 계산하면 된다. 즉 아직 먹지 못한 건초 수 * 걸린 시간 까지 더해서 관리 한다면 앞으로 부패할 값만 계산하면 되고, 완벽하게 관리할 수 있다. 

후기

사수아탕을 푼 적이 있었기 때문에 딱히 어려울 게 없었다! 특히 DP면 뭐...

BOJ 18373 N!!!...! mod P

풀이

케이스 워크를 해야한다. 일단 N>=P 면 답은 0이다.

그 외에 N=2 라면 답은 2이다. 또한 N=3일때 !을 하나 줄이고 N=6이라고 생각하자.

N=4 이상일 때 N!! >5*`10^8 이기 때문에 !이 3개 붙는 순간 답은 0이고 따라서 우리는 4<=N<=13 인 N에 대해서 N!! Mod P의 값만 구하면 된다. 11! 의 값은 3991,6800이기 때문에 $O(N!)$으로 구할 수 있다. 하지만 12!의 값은 4,7900,1600 이기 때문에 다른 방법이 필요해 보인다...

구글신에 (p-1)! mod p 라는 것을 검색해보면 wilson's theorem을 볼 수 있다. 그 내용은 (p-1)! mod p = -1이라는 것. 마침 13!의 값은 문제의 제한인 5,0000,0000과 굉장히 가깝기 때문에 (p-1)! 에서 역으로 구하는 것으로 문제를 해결할 수 있다.

후기

레전드 문제 제한을 볼 수 있었다. 친구들의 도움을 받아서 케웍을 했고, 구글의 도움을 받아 윌슨을 알아냈다... 윌슨을 얻어갈 수 있었던 문제

BOJ 8872 빌라봉

풀이

문제를 읽으면 대충 중앙 쯤에서 연결해야 겠다는 생각을 할 수 있고, 트리에서 모든 점 까지의 거리의 최댓값이 최소인 어떤 점을 잘 잡아야 겠다는 생각을 할 수 있다. 당연히 다른 트리와 연결할 점은 고른 그 점이 될 것이다. 고른 점에서 모든 점 까지의 거리의 최댓값을 트리의 반지름이라고 하자. 

 일단 반지름이 가장 큰 트리의 중심에에 스타 형태의 트리 같이 다른 모든 트리를 붙여야 겠다는 생각을 할 수 있다. 처음에는 그러면 정답이 반지름이 가장 큰 트리의 반지름 + 반지름이 두 번째로 큰 트리의 반지름 + L: 일것이라고 생각을 했으나 트리의 지름 중 최댓값, 혹은 2번째 반지름+ 3번째 반지름 + 2*L 도 답이 될 수 있다.

 반지름을 구하는 방법은 정말 다양하다. 그 중에서 내가 생각한 방법은 꽤나 좋은 방식이라고 생각한다. 일단 트리의 중심(모든 점 까지의 거리의 최댓값이 최소인 어떤 점) 이 트리의 지름 경로 위에 있다는 것을 알아야 한다. 그렇다면 트리의 지름의 양끝점에서 각각 다른 모든 점까지의 거리를 구한 뒤, 그 두 거리중 최댓값이 최소인 점을 찾으면 된다. 또한 그 값이 트리의 반지름이 된다. 이는 https://stonejjun.tistory.com/149 와 비슷한 느낌으로 값이 올바르다는 것을 알 수 있다.

 결국 각 트리별로 dfs를 몇번씩 돌리고 반지름과 지름 값 들을 잘 비교해서 계산해주면 된다.

후기

답이 될 가능성이 있는 값의 후보를 모두 고려하는 과정에서 실수하기 쉬운 문제라고 생각한다. 

BOJ 14749 Grasshopper Route

풀이

트리이기 때문에 편하게 생각하기 위해서 루트를 잡아야 한다. 이 문제와 같은 경우는 일단 루트를 시작점으로 잡아보자.  그렇다면 자식들을 루트로 하는 서브트리가 있을 것이다. 그 서브트리 중에는 목적지가 하위노드로 있는 서브트리도 있을 것이다. 

 그렇다면 방문하는 순서는 목적지가 마지막이어야 하기 때문에 목적지가 하위노드로 있는 서브트리를 마지막으로 들어가야 할 것이다. 이와 별개로 방문은 어떻게 해야할까? 서브트리의 모든 노드를 탐색할 때 할 수 있는 방식은 두가지이다. 서브트리의 루트를 시작할 때 탐색하기, 혹은 마지막에 탐색하기. 
 어떤 서브트리의 루트를 시작할 때 탐색했을 때, 그 자식들을 루트로 하는 서브트리는 루트를 마지막으로 탐색하는 방식을 선택하면 거리 3안에 서브트리의 노드를 탐색할 수 있다. 다른 방식으로는 노드의 레벨을 홀짝으로 나눠서 홀수 레벨은 내려가면서 탐색하고 짝수 레벨은 올라가면서 탐색하면 같은 결과를 얻을 수 있을 것이다. 

후기

stations 라는 문제에서 영감을 얻을 수 있었다. 

BOJ 25095 Weightlifting

풀이

DP를 하는 문제이다. 딱봐도. 구간 DP를 해야할 것처럼 보이는데 중요한건 재귀 DP를 해야하는 것이다. 

prefix 를 이용하여 미리 구간에 대해서 

후기

codejam 때는 못풀었다...

 

지속적으로 갱신 중입니다...