BOJ 2169 로봇 조종하기

N * M 배열에서 로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동이 가능하다. 그리고 한 번 탐사한 지역은 다시 탐사하지 않도록 한다. 그리고 각 배열의 칸에는 숫자(-100 ~ 100)가 적혀있는데, 이 때, (0, 0)에서 (N - 1, M - 1)까지 이동하면서 지나간 칸의 숫자의 합이 최대가 되도록 이동하고, 그 최대값을 구하는 문제이다.

dp를 이용해서 구할 것인데, 예를들어, (r, c)에서 출발해서 (N - 1, M - 1)칸 까지의 칸의 숫자의 합을 구할 때, (r, c - 1), (r, c + 1), (r + 1, c) 칸 중 어느 칸으로 이동해야 숫자의 합이 최대가 되는 경로인지 볼 것인데, 단순히 (row, column) 정보로는 부족하다.

같은 (r, c - 1)라고 해도 직전 경로가 위인지, 왼쪽인지, 오른쪽인지(어디에서 왔는지)에 따라 다음에 갈 수 있는 경로가 다르게 결정된다. 예를들어, 왼쪽에서 왔다고 하면 한 번 탐사한 지역은 다시 탐사하면 안되기 때문에 오른쪽이나 아래쪽으로 가야한다. 그래서 어떤 방향에서 왔는지에 대한 정보가 필요하다.

그리고 dp를 이용해서 풀 때, 평소 dp배열을 -1로 초기화하고 -1이 아니면 답을 구했다고 판단하고 리턴해줬는데, 이 문제의 경우 데이터에 음수값이 있기 때문에, 따로 boolean check배열을 만들어서 이미 그 부분에 대해 답을 구했는지 아닌지 판단한다.

그리고, 또 실수할 수 있는 부분이 있다면, 최대값을 구할 때, max값을 0으로 초기화해놓고, 비교해서 최대값을 구하는 것에 익숙한데, 위에서 말했듯이 음수값이 있기 때문에 0으로 초기화하면 안되고, 모든 입력이 -100으로 들어온다고 가정하고 그에 해당하는 1000 * 1000 * (-100) 으로 max값을 초기화 해줄 필요가 있다.
아니면, 그냥 max값에 바로 구한 값을 대입하면서 시작하는 방법도 있다. 이 방법은 굳이 나올 수 있는 최소값이 얼마일까 고민할 필요도 없고, 그렇기에 실수할 가능성도 적다.

BOJ 14590 KUBC League (Small)

주어진 입력값으로 그래프를 만들었다.
그리고 모든 가능한 경우를 다 확인하고 그 중 최대값을 구한다고 하면...
아마도 n! 만큼의 시간이 걸릴 것이다.

그래서 dp로 접근하기로 했다.
먼저 그래프는 1번vertex부터 시작해서 1번이 이긴 vertex로, 한 vertex에서 그 vertex가 이긴 vertex로... 이렇게 단방향으로 연결되어 있는 directed graph이다.

선수의 나열은 각 선수가 달라야 하므로 방문한 vertex는 다시 방문하면 안되고, 그렇기 때문에 방문한 vertex에 대한 기록이 필요하다. 다행이 n제한이 최대 20이라, 비트마스크를 이용해 상태 dp를 이용할 수 있다.

d[node][state] = 지금까지 방문한 점이 state이고, node에서 시작해서 얻을 수 있는 선수 나열의 최대 길이

d[node][state] = Max( d[next][state | (1<<next) ) + 1

지금까지 방문하지 않은 점 next들을 방문해보면서 그 중 최대인 값을 얻으면 된다.

근데 문제가 하나 더 있다. 바로 선수 나열의 최대길이 뿐 아니라, 선수 나열이 어떤식으로 되어있는지도 구해서 출력해야 한다.

이 부분도 좀 까다로웠는데, 처음에는
nextNode[node] = node의 다음 vertex(node)
로 놓고, Max값이 갱신될 때 nextNode[node]값을 구했는데(갱신했는데), 이럴 경우 문제가 생기는 것 같다.

node와 그에 따른 여러 state의 경우의 수가 존재하는데, 정답에 해당되는 경우가 여러 개일 수 있고, 각 경우마다 nextNode[node]값이 갱신되면 정확한 경로가 나오지 않을 수 있다.

그래서 고민하다가,
nextNode[node][state] = 지금까지 방문한 점이 state일 때, node의 다음 vertex
로 놓고, 나중에 답을 출력할 때, state도 처음부터 시작하여 다음 node에 따라 변경해주면서 선수의 나열을 출력했다. 가장 안전해 보이면서도 좀 무식한? 방법같은데 다른 방법이 떠오르지 않아서... 일단 이렇게 했다.

그리고 추가로...좀 많이 틀리고, 고민을 했는데,
결정적인 이유가 바로 배열의 크기 설정에 있었다. 상태가 0 ~ (2의 20제곱 - 1) 까지 존재하기 때문에 배열에서 다 커버해 줘야 하는데, 나는 배열의 크기를 (2의 20제곱 - 1)로 잡아
0 ~ 2의 20제곱 - 2까지만 커버했고, 그래서 printf를 이용해 디버깅할 때, 도무지 이해할 수 없는 출력 결과가 나왔다. 거의 10시부터 시작해서 새벽 3시까지 고민하다가 오전에 다시 고민해서 배열의 크기 설정이 원인이란 사실을 겨우 발견했다. 감사합니다...

그리고 내 방법은 메모리와 시간 모두 매우 크게 나와서 상위권에 있는 고수님들의 코드를 보려고 한다.

풀이도 보려고 한다. : https://www.acmicpc.net/board/view/15506

BOJ 1219 오민식의 고민

어렵다.
Bellman-Ford algorithm을 사용하면 되긴하는데, 출력 조건에 맞춰 출력하는 부분에서 Bellman-Ford algorithm과 이 문제에 대한 깊은 이해가 필요하고 많은 고민이 필요해 보인다.

판별해야 하는 상황은 다음과 같다.
1. 도착도시에 도착하는 것이 불가능할 때
2. 무한대의 돈을 벌 수 있을 때
3. 도착도시에 도착하는 것이 가능하면서 무한대의 돈을 버는 것은 아닐 때

다음과 같이 판별해볼 수 있겠다.
1. 출발도시에서 도착도시까지 도달하는 것이 불가능하다면 upper값으로 설정한 NEGINF에 100만씩 100번 완화할 수 있으므로 upper[des]값이 NEGINF인 경우만 도달 불가능하다고 보면 안되고, NEGINF+100*1,000,000 이하인 경우를 도달 불가능하다고 봐야할 것이다.
- JM book 참고하기

2. 단순히 양수 사이클이 있는 경우라고 생각하기 쉽다. 하지만 아니다.
양수 사이클이 존재하면서 그 양수 사이클에서 도착도시까지 갈 수 있어야 한다.
양수 사이클이 존재하지만 양수 사이클에서 도착도시로 갈 수 없다면 돈을 벌 수 없기 때문에 그 경우는 양수 사이클로 가지말고 도착도시로 가야한다.

3. 사이클이 없거나, 사이클이 있더라도 그 사이클에 빠지면 도착도시로 갈 수 없는 경우이다.

** 2, 3을 구별해서 하는 것이 문제이다. 사실 이것들을 생각하지도 못했는데, 질문 게시판에 있는 고수들의 질문과 답변을 보고 알았다.


실제 테스트할 때는,
4 0 3 4
0 1 0
1 2 0
2 1 0
0 3 10
10 10 10 10 으로 테스트 해보면 된다.









만약 사이클이 있고 그 사이클에서 도착도시까지 연결돼 있다면 n번째 갱신할 때, 도착도시까지 가는 경로가 갱신될 줄 알았는데... 이 예제를 보면 그렇지 않다는 것을 알 수 있다!

사이클이 있는지는 판단하기 쉽지만, 그 사이클에서 도착도시까지 갈 수 있는지 없는지를 판단하기가 어렵다. 어떻게 해야할까?

일단 사이클이 있다면 n번째 갱신할 때, 사이클에 포함된 도시가 갱신될 것이다. 그럼 그 도시부터 시작해서 도착도시까지 갈 수 있는지 dfs로 알아보면 될 것 같다. -> 생각해보니 n번째 갱신할 때 사이클에 포함되지 않은 도시도 갱신될 수 있을 것 같다... 그럼 어떻게 사이클에 포함된 도시를 알 수 있을까? -> 잘 모르겠지만, 이 문제에서는 사이클에 포함된 도시를 골라낼 필요가 없다. n번째 갱신할 때, 갱신되는 도시중에는 사이클에 포함되지 않은 도시도 있겠지만, 그 도시는 사이클로부터 온 도시일 것이다. 결국, n번째 갱신할 때 갱신되는 도시가 어떤 도시든 그 도시에서 도착도시까지 갈 수 있다면, 사이클에서 도착도시까지 갈 수 있는 것이다....

그리고, 사이클이 있으면 시작도시에서 사이클이 있는점까지 갈 수 있는지도 체크해야 한다.좀 간편하게 하기위해 플로이드와샬로 각 도시간에 이동할 수 있는지를 체크해놓는 것도 괜찮고, 아니면 벨만포드를 구현할 때, here, there가 있어서 here를 이용해서 there를 갱신하는데, here가 NEGINF(INF)인 경우(즉, 시작점에서 here까지 도달 못한 경우) 갱신이 안되게 하면, 사이클이 있어도 시작점에서 갈 수 없는 사이클이라면 사이클을 찾아낼 수 없을 것이다.
그리고 이렇게 구현하면 좋은 것이, 도착도시에 도달할 수 없는지 판단할 때 그냥 NEGINF(INF)인지 아닌지만 보면된다.
이런 구현 방식은 kks227님 블로그를 참조했다.

 그래서 난 일단 here가 NEGINF(INF)인 경우 갱신이 안되게 하고, n번째 갱신할 때 갱신되는 도가 있다면(사이클이 있다면) 갱신되는 점들 중 하나라도 도착도시와 연결이 된다면 돈을 무한히 벌 수 있는 것으로 판정할 것이다.

일단 AC를 받았다.
벨만포드에 대해 잘 알고있다고 생각했는데... 전혀 그렇지 않았고... 오히려 배웠다.
정말 공부가 되는 좋은 문제이다... 나중에 꼭 다시 풀어보기. 생각해보기.

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

BOJ 1022 소용돌이 예쁘게 출력하기

출처 : BOJ Slack

나중에 풀어봐야 겠다.