BOJ 1092 배

까다롭다...

주어진 박스들을 무게에 따라 나눠보자.
어떤 박스는 주어진 크레인들 중 어떤 것으로도 운반하지 못할 수 있고, 어떤 박스는 운반 가능한 크레인이 1개, 어떤 박스는 어떤 크레인으로도 운반 가능할 것이다.

이렇게 박스들을 운반 가능한 크레인 개수에 따라 나눈다.
예를들어, 3종류의 크레인이 있다고 하자.
그룹1 : 크레인 중 1개의 크레인으로만 운반할 수 있는 박스들은 항상 그 크레인으로만 옮길 수 있으므로 전체 박스를 다 옮길 때, 최소한 그 박스들의 개수만큼의 시간이 걸릴 것이다.

그룹2 : 2개의 크레인으로 운반할 수 있는 박스들을 보자.  2개의 크레인을 사용할 수 있긴해도 이 중 1개의 크레인은 첫번째 그룹(1개의 크레인만 운반 가능한 박스들)의 박스를 운반해야 한다. 만약 그룹1의 박스보다 그룹2의 박스가 더 많다면 전체 박스를 다 옮길 때, 최소한 2개의 크레인으로 (그룹1의 박스 수 + 그룹2의 박스 수) 만큼의 박스들을 옮기는 시간이 걸릴 것이다. 여기서 그룹1의 박스가 더 많으면 어차피 그룹1을 1개의 크레인으로 옮기는 시간이 걸리니까 전체 박스를 옮기는 데 걸리는 시간을 구하는 것에는 지장이 없다.

그룹3 : 3개의 크레인으로 운반 가능한 박스들 역시, 3개의 크레인을 사용할 수 있긴해도 1, 2크레인을 그룹 1, 2가 사용하게 되면 결국 1개의 크레인밖에 못쓴다. 만약 그룹 1 또는 2의 박스가 그룹 3의 박스보다 많으면 위에서 이미 계산했던 시간이 답이 될 것이다.
하지만 그룹 3의 박스가 더 많다면 (그룹1 박스 수 + 그룹2 박스 수 + 그룹3 박스 수)를 3개의 크레인으로 옮기는 시간이 걸릴 것이다.

즉 이 세가지 시간 중 최대값을 구하면, 전체 박스를 옮기는 최소 시간을 구할 수 있다.

구현도 좀 헷갈리고... 좀 어려운면서 좋은 문제같다.

BOJ 10837 동전 게임

쉬워보였지만... 적어도 나한테는 여려운 문제였다. 엄청 오래 고민했다.
인터넷에서 찾은 KOI solution에는 코드밖에 나와있지 않아서... 이해를 못했다.
결국 내가 생각해서 AC를 받긴했다.

깔끔한 풀이는 아니지만... 좀 먼 길 돌아가는 풀이 같긴하지만 기록해 보려고 한다.

내가 헷갈렸던 것인데, 일단 문제에서 요구하는 것은 이길 수 없는 점수인지가 아니라 나올 수 있는 점수인지 아닌지 판별하는 것이다.

승패가 결정이 나면 더이상의 게임 진행을 하지 않으므로 주어진 점수 a : b가 불가능한 점수이려면 a : b 바로 이전의 점수에서 승패가 결정나야 한다. 그렇지 않으면 가능한 점수일 것이다.

그런데 a : b 바로 이전의 점수는 어떻게 정할까?
a > b일 경우 a-1 : b를 이전 점수로, a < b인 경우 a : b-1을 이전 점수로 설정한다.
즉, 최대한 차이가 덜 나는 점수, a : b가 성립할 수 있는 가능성이 가장 큰 점수로 직전 점수를 선정하는 것이다.

그리고 게임 순서는 a>b, a-1 : b인 경우는 b가 할 차례이고, a<b, a : b-1인 경우는 a가 할 차례이다. 이것도 역시 a : b가 성립할 가능성이 가장 크도록 설정한다.

a > b인 경우는 a가 이긴 상태로 끝난 것이므로 a-1 : b에서 b가 남은 라운드에서 모두 점수를 얻고, a는 남은 라운드에서 점수를 전혀 얻지 못해도 a가 이길 수 있는지 봐야한다. 그렇게 해도 a가 이기게 되다면 a-1 : b에서 끝내야 하므로 a : b까지 갈 수 없다. 그리고 만약 비기는 결과가 나온다해도 a : b까지 갈 수 없다. 비기려면 b는 모든 라운드에서 점수를 따야 하는데, a : b를 만들기 전에 b가 한 라운드에서 점수를 못 얻으면 a-1 : b에서 a의 차례가 되고 이 경우는 b가 이길 수 없게 되는 것이므로 a-1 : b에서 끝나게 된다.

a > b인 경우랑, a < b인 경우랑 조금 다른 점은 누구 차례인지랑 그에 따라 남은 라운드 수가 좀 다른 것이다. 주의해서 코딩해야하고, a=b인 경우는 (입력 값으로 a, b모두 k이하의 값이 주어지므로) 항상 가능한 경우일 것이다.

KOI solution에 나오는 풀이를 이해하고 싶은데 아직은 이해 못 하겠다.
나중에 기회가 되면 다시 생각해 봐야겠다.

BOJ 2585 경비행기

이분 탐색으로 풀면되는 문제이다. 하지만 조금 까다로워 보이는 것이 있다.
바로 최대 허용 중간급유 횟수 k이다.  연료통의 최소 용량을 구하기 위해서는 k번의 급유를 다 이용하는 것이 좋을 것이다.

일단, 이분 탐색을 이용해서 연료통의 용량을 정하고 그 용량으로 k번이하의 급유를 해서 시작점부터 도착점까지 갈 수 있는지를 따져봐야 하는데, 시작점부터 도착점까지 갈 수 있는지를 따져보는 것이 까다롭다....고 생각했다.  k때문에...

dfs나 bfs를 사용하면 될 것인데, 문제는 어디서 급유를 할 것인가... 즉, k번의 급유를 어떤 비행장에서 써야할 것인가...였다.
주어진 연료의 양으로 k번 이하의 급유를 해서 도착점까지 가려면 연료통에 연료가 남아있어 다음 비행장까지 갈 수 있다면 급유를 하지 않고 계속 가야할 것이다. 그래야 정말 필요할 때 급유할 기회를 사용할 수 있다. 즉, 정말 필요할 때만 급유를 하는 식으로 해야할 것이다.
그래서 dfs를 이용하되 parameter로 연료통에 남아있는 연료량도 넘겨주면서... 근데 거리가 실수로 나오기 때문에 급유없이 가면서 남아있는 연료량을 계산할 때 실수로 인한 오차는 어떻게 처리할까?..도 문제였다.

일단 그냥 코드를 짜서 제출해 봤는데 AC를 받긴했다. 그리고 다른 사람들 코드랑, 공식 답안을 봤는데 나처럼 k번의 급유를 언제 할 것인지를 크게 신경쓰지 않은 것 같았다.
그래서 생각해보니... 아...

모든 비행장끼리는 다 직선거리로 이동이 가능하고, 모든 경우를 다 보는데 어떤 지점까지 갈 때, 연료가 남아서 어떤 지점까지 여러 군데를 거치며 급유없이 간다고 했을 때, 내 원래 생각은 급유없이 가니까 사용되는 연료를 빼주면서 (최대한 급유없이 오래 갈 수 있도록) 가는 것을 코딩하려 했는데... 그럴 필요가 없다. 여러 군데를 거쳐 어떤 지점까지 갈 필요 없이 그냥 바로 그 어떤 지점으로 가면 되기 때문이다! 그리고 바로 가는 것이 직선거리가 되어 연료도 더 조금 들 수 밖에 없다!!!

결국 k번의 급유 기회를 언제 어떻게 사용할지 신경 안써도 된다. 모든 경우를 다 보기 때문에 각각의 경우마다 급유를 하는 것으로 처리해도 된다!

이것이 이 문제의 핵심이 아닐까 생각한다.
아, 그리고 나는 dfs로 코드를 짰는데, 그러면 어떤 지점까지 다른 지점들을 거쳐 돌아가는 경우를 먼저 탐색하게 될 경우 그 지점까지 바로 가는 경우를 못 보게 된다.

그래서 공식 코드에서도 bfs를 사용하는 것 같다.

결론
1. 돌아가는 것보다 바로 가는 것이 항상 더 낫기 때문에 매번 급유를 받는 것으로 해도 상관없다. k번의 급유 기회를 언제 사용할지 신경쓰지 않아도 된다!
2. dfs를 이용하면 더 나은 경우를 못보게 될 수 있으므로 bfs를 사용해야 한다.

그리고 각 지점간의 거리를 double형으로 만들어서(sqrt) 연료량과 비교하는 대신 그냥 int형으로 제곱에 해당되는 값끼리 비교하면 시간이 좀 덜 걸린다. 그리고 int형으로 해도 상관없는 것이 k번의 급유 기회를 언제 사용할지 신경쓰지 않아도 되기 때문이다. 만약 남은 연료량을 계산해야 했다면 int형으로 하기 힘들 것 같다.(물론 double형이라도 오차를 어떻게 처리할 것인가도 문제겠고...)
좋은 문제같다.

BOJ 13304 방 배정

정답률도 높고 풀고보니 어려운 문제는 아니지만... 나한테는 좀 어려웠다.
나는 코드가 좀 지저분한데 다른 분들 코드를 보면서 알게된 것을 간단히 적어보겠다.

몇개의 방이 필요한지 알아보려고 하는데 (학생 수) / (방 수용가능 인원) + ( (학생 수) % (방 수용가능 인원) ? 1 : 0 ) 이런식으로 해서 계산했는데

(학생 수) + (방 수용가능 인원-1) / (방 수용가능 인원) 으로 간단히 계산 가능하다!
1. n/k + (n%k ? 1 : 0)
2. n + (k-1) /  k