머그컵 후기

알바가기전에 BOJ에 머그컵이라는 대회가 열려있길래 참가했다.

총 8문제중 5문제를 풀었는데 나머지 3문제는 내 수준에서는 해결할 수 없는 문제였다.

<C 자원 캐기>

출발 지점에서 끝 지점 까지 최대로 수집 가능한 자원을 찾는 전형적인 다이나믹 프로그래밍 문제였다. 

점화식은 dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j] 다.

<B 배스킨라빈스31>

항상 주어지는 조건대로 게임을 할 때 가장 빨리 끝나는 게임과 번호를 출력하는 문제이다.

수식에 따라서 계산을 해주면 게임의 횟수는 ((k/(m+1))+1)*2 가 될 것이고 set을 이용하여 관리를 해주면 편하게 해결 가능했다.

<D 소수마을>

마을의 위치가 좌표로 주어질 때 각 마을 사이의 거리의 정수부분이 소수일 경우 이동가능하다고 할 때 A부터 B까지의 최단거리를 출력하면 되는 문제였다.

에라토스테네스의 체를 이용하여 소수들을 구해준 후 모든 좌표들의 거리를 비교하여 소수일 경우 간선을 연결해준다. 이후 다익스트라를 통하여 최단거리를 구해주었다.

<F 한조 대기 중>

두 이분 그래프에 대해서 최대매칭을 비교해주면 되는 문제였다. 

N이 300밖에 안되었기 때문에 이분매칭을 두번 돌려준 후 최대매칭을 서로 비교해주어서 답을 출력했다.

<A 준오는 심술쟁이!!>

경우의 수를 구하는 문제였기 때문에 다이나믹프로그래밍으로 접근했으나 O(3000*3000*25)라는 애매한 시간때문에 TLE를 받았다. 

재귀함수에 모듈러 연산까지 호출하기에는 큰 연산횟수였던거 같다. 

포문으로 수정한 뒤 dp[i][0]~dp[i][j] 를 파셜섬으로 저장하여 25의 연산을 줄여준 뒤 O(3000*3000)의 시간에 해결하였다.

무려 12번이나 제출한 문제이다 ..

코드포스도 잘 안하는데 이런 대회에 참가할 기회가 있어서 재밌었다.