March 20, 2022 08:00

알고리즘 문제 접근 과정 9

이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다.

최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다.

짐 정리 - KOI 2007 지역본선 중등부 4번

풀이

문제를 간략화하기 위해, 짐들을 옮길 때 드는 힘을 생각하지 않고, 최소 몇 번 만에 짐을 옮겨 정렬할 수 있는지 위 그림을 예시로 확인해봅시다.

i) 각각의 짐들은 자기 위치에 있거나, 혹은 자신의 위치에 있지 않은 두 가지 경우가 있다. 자기 위치에 있는 짐은 어차피 옮겨봤자 그 위치로 오게 된 다른 짐과 자기 자신 모두 제 위치로 다시 돌아가야하므로 항상 횟수를 더 늘리게 되어 의미가 없다. ii) 자신의 위치에 있지 않은 짐의 경우, 한 번 옮기는 것으로 자신의 위치로 돌아갈 수 있다. 이 때 옮겨진 다른 짐은 그 위치가 자신의 올바른 위치이거나 아닌 두 가지 경우가 있기 때문에, 한 번의 바꿈에 최소 1개, 최대 2개의 짐이 정리된다는 것을 알 수 있다. iii) 만약 두 짐을 바꾸어도 둘 다 올바른 위치로 가지 않는 경우, 이 때에도 두 번의 바꾸기를 어차피 더 처리해야 하므로 횟수를 늘리게 되어 무의미한 바꿈이 된다.

즉, 이를 통해 우리는 항상 한 번 바꿀 때, 적어도 하나의 짐은 정리될 수 있게 바꿔야한다는 것을 알 수 있다. 그럼 위 예시에서 최소 횟수로 바꾸어 짐을 정리해봅시다.

2번 짐의 경우 10번 짐의 위치로, 10번 짐은 5번, 5번 짐은 2번 짐의 위치로 이동해야합니다. 이를 그림으로 그리게 되면 2 -> 10 -> 5 -> 2로 이어지는 사이클이 만들어집니다.

이 때, 사이클의 한 선이 서로 잇지 않는 짐들을 옮기는 경우는 iii)번 경우와 같기 때문에 의미가 없게 됩니다. 즉, 우리는 항상 바꿀 때마다 간선의 양 옆에 해당하는 짐들을 바꾸는 것으로 짐을 정리할 수 있고, 최종적으로 필요한 연산의 수는 (사이클 간선의 수 – 1)이 됩니다(나머지 경로에서 짐들이 모두 바뀌기 때문에, 마지막 한 번 더 바꾸게 되면 두 짐은 한 번 더 바뀌게 된다).

즉, 우리가 정리에 필요한 최소 연산은 위 방법으로 만든 (사이클 간선의 전체 수 – 사이클의 수)가 됩니다.

그렇다면, 이 때 힘을 고려하면 어떻게 바꿀 수 있을까요? 만약 한 사이클 내에 있는 짐들만 서로 교환해서 바꾼다면 어떻게 바꾸는 것이 좋을까요?

물론 여기에서 어떤 순서로든 항상 하나가 정렬되도록 바꾸면 5번만에 해결할 수 있습니다. 즉, 이 때 적어도 모든 짐들은 한 번씩 이동해야하므로 2 + 6 + 1 + 4 + 9 + 10의 비용은 최소한으로 들게 됩니다. 그렇다면 각 짐들을 정렬하기 위해 비교하는 다른 한 짐은 어떤걸 선택하는게 좋을까요?

위 사이클을 오른쪽으로 두 번 돌려봅시다.

이 때, 6번부터 1번과 바꾸기 시작한다면, 바꾸는 연산은

와같이 됩니다.

여기서 무언가 볼 수 있을까요? 나머지 한 쪽에는 1을 제외한 모든 짐들이 들어가고, 다른 한 쪽에는 1만을 들어가게 할 수 있습니다. 즉, 힘은 (모든 짐들의 합 + 다른 쪽 짐 * (바꾸는 횟수 – 1)) 만큼 필요합니다. 이 때, 다른쪽 짐을 항상 그 사이클 내 가장 작은 짐으로 고정해놓는다면 한 사이클 내에서만 짐을 바꾼다고 했을 때, 항상 최소로 바꿀 수 있습니다.

그렇다면, 모든 사이클에 대해 이 방법을 쓰는 것이 최소일까요?

다음 예시를 한 번 봅시다.

위와 같은 두 사이클이 존재한다고 할 때, 아래 사이클은 당연히 1 – 2를 바꾸는 것이 최적임을 알 수 있습니다.

그렇다면, 윗 사이클의 경우는 어떨까요?

앞서 한 것처럼 가장 작은 짐을 기준으로 하면 들어가는 힘은 (510 + 100 * 3) = 810이 들어갑니다. 하지만 다음과 같이 바꾸면 어떻게 될까요?

이 경우의 합은 (모든 짐들의 합 + 100 + 1 * 6) = 602만큼 들어가게 됩니다.

위 경우는 나머지 중에 가장 작은 짐을, 한 사이클 내 가장 작은 짐과 바꾸어 한 쪽 짐을 가장 작은 짐으로 고정시켜 정렬한 이후, 사이클이 정렬되고 나면 원래 사이클에 있던 짐과 다시 자리를 바꾸는 방법입니다. 이 경우, 전체 중 최소인 짐을 여러 번 쓰게 되지만, 그 짐의 무게 자체가 작을 경우 이득을 볼 수 있는 방법입니다.

그렇다면, 위 두 경우가 나머지 모든 경우들보다 항상 낫다고 말할 수 있을까요?

정렬을 할 때에는 항상

• 한 사이클 내 짐들만 이용하거나
• 다른 사이클 내 짐을 이용하는 것

이 두 가지가 있으므로, 각각의 경우에 가장 작은 짐을 쓰는 것은 항상 유의미하고, 이외의 경우들은 위 경우에 속하면서 값이 더 커진다는 것을 알 수 있습니다. 즉, 우리는 각 사이클 내 가장 작은 원소의 값과, 한 사이클의 크기와 원소들의 합, 모든 짐들 중 최솟값을 알고 있다면, 한 사이클을 정렬하는데 필요한 비용을 한 번의 계산만으로 알아낼 수 있습니다.

사이클을 찾아내는데 $O(N)$, 각 사이클을 탐색하는데 총 $O(N)$, 짐들의 원래 위치를 찾기 위해 정렬하는 시간 $O(NlgN)$이 필요하므로 최종 시간복잡도 $O(NlgN)$에 문제를 해결할 수 있습니다.

새로운 님게임 - 2019년 한국정보올림피아드 1차대회 고등부 문제 유형2 7번

해당 문제는 필기 문제이므로, 임의의 문제 상황을 만들어 설명하겠습니다.

문제

알고는 리즘이와 님게임을 하는 중이다.

님게임이란, 2개의 각 줄에 바둑돌을 n개씩 두고, 한 사람이 한 줄을 선택하고, 그 줄에서 원하는 만큼의 바둑돌을 가져가고, 그 다음 사람이 똑같은 일을 수행해나가다가, 마지막 바둑돌을 가져가는 사람이 지는 게임이다.

알고와 리즘이는 님게임을 하다가, 이 게임이 너무 쉽다는 것을 알게되고, 금방 흥미를 잃게 되었다.

둘의 게임을 지켜보던 해결이는, 알고와 리즘이에게 ‘새로운 님게임’을 하자는 의견을 제시했다.

새로운 님게임이란, 이전과 같이 2개의 각 줄에 n개의 바둑돌이 일렬로 놓여있으며 한 줄을 선택하여 돌을 가져가며, 가져가는 돌의 수는 제약이 없다.

첫 줄을 선택하여 돌을 가져가는 경우, 이전과 동일하게 그 줄에서만 돌을 가져가게 되지만, 만약 두 번째 줄에서 선택하여 돌을 가져가는 경우, 두 번째 줄에 남아있는 돌의 수가 첫 번째 남아있는 돌의 수보다 적다면, 첫 줄의 돌의 수를 두 번째 줄의 돌의 수와 같게 되도록 돌을 추가로 더 가져가야한다.

새로운 님게임을 들은 알고와 리즘이는 재미있을 것 같다고 생각하여 게임을 하게 되었다. 이를 접한 알고와 리즘은 게임을 바로 이해하고 재미있게 하게되었다.

둘이 게임을 하는 것을 보고있는 해결이는, 둘이 게임을 하고있는 도중에, 누가 이길지 예측하고싶어하지만, 해결이는 게임을 잘 이해하지 못하여 누가 이길지 알지 못해, 도움을 요청했다.

첫 줄과 두 번째 줄에 놓여있는 돌의 수가 주어지며, 알고가 돌을 가져갈 차례일 때, 알고와 리즘이 중 누가 이길지 해결이에게 알려주자.

예시

첫 줄에 돌이 1개, 두 번째 줄에 돌이 2개라면 알고가 어떻게 해도 리즘이를 이길 수 없으므로, 리즘이가 이기게 된다.

관찰

우리가 흔히 상대방이 어떤 식으로 게임을 진행할지 알기 어려운 경우에 항상 최선을 다해서 게임을 진행한다는 형태의 문제를 접하고, 그 게임의 필승전략을 알지 못한다면, 상대방이 진행할 수 있는 경우가 가장 적은 작은 문제상황에서부터 접근을 해야합니다.

이 때, 작은 상태에서 먼저 게임을 시작하는 사람이 어떻게 해도 지는지, 혹은 어떻게 해도 지는지, 어떻게 상태를 만들면 이기는지에 대한 정보를 아는 것이 중요합니다.

주어진 예시인 각 줄에 1, 2 개의 돌이 있는 경우부터 살펴보겠습니다. 각 줄의 돌의 수를 (a, b)의 형태로 나타내겠습니다.

만약 (1, 2)의 상태에서 알고가 첫 줄의 돌을 가져가 (0, 2)가 된다면, 리즘이는 (0, 1)을 만들어 게임을 이길 수 있고, 알고가 (1, 1)의 상태로 만들더라도 리즘이가 (0, 1)의 상태를 만들면 이기므로, 알고는 어떻게해도 게임을 이길 수가 없습니다.

하지만 이 말은, 만약 알고가 어떤 돌의 상황에서 돌을 가져가서 리즘이한테 (1, 2)인 돌의 상태를 준다면, 알고가 무조건 승리한다는 말이 되기도 합니다.

즉, 우리는 항상 필승을 할 수 있는 상태로 ‘상대에게 (1, 2)를 준다’ 라는 한 경우를 찾아볼 수 있었습니다.

그렇다면, 항상 알고가 이길 수 있는 상태들을 찾아볼 수 있을까요?

우리는 첫 줄에서 원하는 만큼 돌을 가져갈 수 있기 때문에, 1보다 큰 수 a에 대해, (a, 2)의 상태인 경우 항상 알고가 첫 줄에서 a-1개의 돌을 가져가 (1, 2)의 돌을 리즘이한테 넘겨줘 게임을 이길 수 있습니다.

다만, 새로운 님게임의 조건 때문에 항상 첫 돌의 수가 두 번째 돌의 수보다 많은 경우는 없으므로, 알고가 이길 수 있는 조건을 현재 (2, 2)가 유일할 것입니다.

또는 2보다 큰 b에 대해서, (1, b)의 상태일 때 b-2개의 돌을 알고가 가져가서 이길 수 있으므로, 알고는 (2, 2), 혹은 (1, b)의 상태에서 게임을 이길 수 있습니다.

즉, 리즘이는 알고에게 (2, 2), 또는 (1, b)를 넘겨주는 상황이 항상 게임을 지는 경우임을 알 수 있습니다.

우리는 이처럼, 우리가 고려할 수 있는 작은 상태에서부터 어떤 상태들의 결과를 알 수 있는지 차근차근 생각해볼 수 있습니다.

풀이

이제 우리는 (2, 2), (1, b)의 경우 알고가 이길 수 있다는 사실을 알게 되었습니다. 우리는 이것을 확장하여 나중에 (a, b)에 해당하는 판의 승자를 알 수 있다면, 어떠한 경우에서도 답을 알아낼 수 있습니다.

앞선 관찰의 확장방법과 동일하게 한 단계씩 생각해봅시다.

만약 알고가 (2, b)의 판을 가지고 있다면 어떻게 될까요? 첫 줄에서 1개의 돌을 가져가면, 리즘이가 두 번째 둘의 돌을 1개 빼고 모두 가져가면 되므로 안됩니다. 또한, 두 번째 줄의 돌을 가져가 (2, 2), (1, 1)의 돌만 남겨놓더라도 항상 지게 됩니다. 즉, 우리는 상대방이 가질 때 가장 어려운 상태를 만들어서 돌려줘야합니다.

만약 b가 3이라면 어떻게 될까요? 어떻게 해도 알고는 (1, 1), (2, 2), (1, 3)의 상태를 벗어날 수 없고, 이 상태는 모두 상대방의 승리가 보장되어있습니다. 즉, 우리는 (2, 3)의 경우 항상 진다는 것을 알 수 있습니다.

그렇다면, b가 4 이상이라면? 알고가 (2, 3)의 상태를 만들어서 리즘이한테 넘겨주면, 알고가 승리하게 됩니다! 우리는 새로운 상태로, (2, 3)의 상태가 필패임을 찾았습니다.

(3, b)의 경우까지 한 번 더 고려해보도록 합시다. 만약 (3, 3)이라면 (2, 3)을 만들어 상대를 이길 수 있게 되며, (3, 4)라면 (2, 4)를 만들어도 리즘이가 (2, 3)을 만들며 지고, (3, 3)을 만들어도 지며, 나머지 상태들 모두 진다는 것을 이미 이전에 확인한 적이 있어서, (3, 4)는 필패임을 알 수 있습니다. (3, 4)가 필패이므로, 우리는 (3, b)에 대해 b - 4개의 돌을 두 번째 줄에서 가져가면 항상 필승이 됨을 알 수 있습니다!

우리가 구한 필승, 필패 상태를 판에 나타내봅시다.

우리가 구한 알고가 승리, 패하는 상태들을 나타낸 표입니다.

혹시, 이 규칙은 우연일까요? 우리가 (a, a+1)인 상태의 판은 항상 지고, 나머지의 경우 이기는 것이 우연일까요?

결과부터 이야기하자면 절대 우연이 아닙니다.

이는 귀납적으로 증명할 수 있습니다.

우리는 이미 관찰 과정을 통해, (1, 1)이 필승상황, (1, 2)가 항상 필패상황이라는 것을 알 수 있었습니다. 이를 이용하여 우리는 다음 3가지를 증명하도록 합시다.

• (a, a+1)이 필패상태라면, (a+1, a+1)은 필승상태이다
• (a, a+1)이 필패상태라면, (a, a+b) (b >= 2)은 필승상태이다.
• 1, 2번을 만족한다면, (a+1, a+2)는 필패상태이다

위 3가지를 증명한다면, 우리는 (1, 2)이 필패상황임을 이용하여 (2, 2)가 필승, (1, 3) 이후는 필승임 알 수 있고, 새로 (2, 3)이 필패임을 통해 이를 무한히 반복하여 항상 (a, a+1)을 제외하고는 필승상태임을 증명할 수 있습니다.

첫 번째부터 증명하겠습니다. (a, a+1)이 필패라면, (a+1, a+1)에서 첫 번째 줄에서 돌 한 개를 가져가서 항상 (a, a+1)을 상대에게 넘겨줄 수 있으므로, 상대는 필패하여 나는 필승할 수 있습니다.

두 번째 상태의 경우, (a, a+1)이 필패라면, (a, a+b)에서 두 번째 줄에서 b - 1개의 돌을 가져가면 상대에게 필패상태를 줄 수 있어, 나는 필승하게 됩니다.

이제 문제의 첫 번째를 증명하겠습니다. 현재 a보다 작거나 같은 c들에 대해서는, 항상 (c, c+1)을 제외하고는 (a+1, a+2)보다 작은 상태들에 대해 항상 먼저 게임을 하는 사람이 필승이라는 점이 귀납적으로 보장되었다고 합시다.

이 때, (a+1, a+2)에서 할 수 있는 경우들을 하겠습니다.

두 번째 줄에서 1개 이상의 돌을 가져간다면 항상 특별한 (c, c)의 상태가 되므로, 상대가 필승이 되어 먼저 게임을 한 사람은 지게됩니다. 첫 번째 줄에서 1개 이상의 돌을 가져간다면, 항상 c보다 2 이상 큰 d에 대해 (c, d)의 상태가 되므로, 이는 2번에 해당하는 경우이므로 상대방이 필승이 되어, 먼저한 사람은 지게됩니다.

즉, 어떻게 해도 먼저한 사람은 게임을 지게 되므로, (a+1, a+2)는 필패가 됩니다.

이를 통해 모든 경우가 다 귀납적으로 해결이 되어, 항상 (a, a+1)의 꼴을 제외하고는 먼저한 사람이 게임을 이기게 되며, 이 경우는 항상 게임을 지게 됩니다.

이를 이용하여 입력 상황을 구분해주면 되며, 우리는 $O(1)$에 문제를 해결할 수 있습니다.

[차고지]

문제의 원본 출처를 잊어 링크를 첨부하지 못했습니다. 해당 문제를 알게 된다면 추가하겠습니다. 문제 상황 및 입출력 조건을 첨부하여 풀이를 진행하겠습니다.

문제

알고는 차고에 일렬로 있는 N개의 차들을 모두 팔기 위해 중고로 올려놨고, 다행이도 모든 차들에 대해 판매가 완료되었다. 하지만 각 차들을 구매하는 사람들은 모두 달랐고, 이에 가장 먼저 팔리는 차부터, 가장 늦게 팔리는 차까지 1번부터 N번까지 순서대로 매길 수 있었다. 허나 알고의 차들은 차고에 일렬로 놓여있기 때문에, 1번 차 앞에 다른 차들이 막고있어 순서대로 빼낼 수가 없는 경우가 있었고, 이를 해결하기 위해 알고는 일렬로 차를 세울 수 있는 다른 M개의 차고지를 이용해 순서대로 차를 입구를 통과해 보낼 수 있게 하려한다. (단, 다른 차고지로 보낸 차량은 다시 다른 차고지로 옮길 수 없고, 바로 입구로 빠져 나가야한다)

예를 들어, 가장 오른쪽에 있는 차가 먼저 나갈 수 있고, 5, 2, 3, 1, 4 순서로 놓여있을 때, 추가로 1개의 차고지가 있다면, 4번을 차고지로 옮긴 후 1번을 보내고, 3번을 차고지에 넣을 후, 2번을 보낼 수 있다. 이후 다른 차고지의 마지막에 있는 3번차를 옮긴 후, 4번 또한 옮길 수 있게 된다. 이후 원래 차고지의 5번 차를 보내면 순서대로 1~5번 차가 입구를 통과해 보낼 수 있게 된다.

알고는 차들을 옮기는데 정신이 없어, 순서대로 보내는 방법을 우리에게 부탁했다. N개의 차량과 M개의 빈 차고지가 있을 때, 알고가 순서대로 보내는 것이 가능한지 알려주자.

입력 형식

첫 줄에 차량의 수 N과 빈 차고지의 수 M이 빈칸을 사이에 두고 주어진다. (1 <= N, M <= 5000) 두 번째 줄에 현 차고지에 놓인 차량의 번호 N개가 일렬로 주어진다.

출력 형식

순서대로 보내는 것이 가능할 경우 1을, 불가능할 경우 0을 출력한다.

관찰

만약 차들이 1번부터 n번까지 순서대로 놓여있다면, 우리는 그 차들을 그 순서대로 바로 통과시켜도 순서가 맞게 보낼 수 있습니다. 그렇다면, 어떤 상태에서 차를 바로 통과시킬 수 없게 될까요?

예시를 보면, 1번부터 2, 3번까지는 순서대로 차를 통과시켰습니다. 허나, 3번 차 바로 뒤에 있는 차는 6번차여서, 3번 차 뒤에 바로 보낼 수가 없었습니다. 이 때에, 우리는 6번차를 바로 보낼 방법이 없기 때문에, 어떻게 되었든 한 번은 주차장으로 들어가야 한다는 것을 알 수 있습니다.

즉, 우리는 어떤 n번 차가 바로 통과될 수 없을 때(그 차의 앞번호들이 현재 아직 통과하지 못했을 때)에는 무조건 주차장으로 보내야먄, 그 뒤에 있는 앞번호 차량들을 보낼 수 있다는 것을 알 수 있습니다. 이를 통해, 차가 주차장에 들어오는 조건은 ‘현재 차가 바로 통과될 수 없을 때’가 됩니다.

그렇다면, 차가 주차장에서 빠져나가는 조건은 어떻게 될까요? 차는 주차장에서 나오면 바로 길을 통과해야하고, 길을 통과할 수 있다는 것은 ‘주차장 맨 뒤의 차가 앞서 나간 차의 바로 다음 번호’ 라는 뜻이 됩니다.

그렇다면, 현재 차가 통과할 수 있는 상태라면 어떻게 해야할까요? 우리가 현재 차를 통과시킬 수 있다는 것은, 이보다 더 작은 번호의 차들은 이미 빠져나갔다는 소리가 되고, 나머지 차들은 현재 차보다 항상 번호가 크다는 것을 의미합니다. 즉, 이 차가 나가지 않는 이상, 다른 차들은 나갈 수 없게 되고, 현재 차가 나간다고 해서 다른 차들이 나갈 수 없는 경우는 발생하지 않습니다(이미 현재 차의 번호가 다른 차들보다 더 작으므로). 그러므로 우리는 현재 차를 무조건 통과시켜야 합니다.

매 순간, 이동이 가능한 차들은 항상 주차장의 맨 뒷 차들이거나, 혹은 차고지 맨 앞의 차만 해당되고, 각 차들은 윗 경우들 중 한 경우에 무조건 포함된다는 것을 알 수 있습니다.

즉, 우리는 앞선 관찰을 통해 언제 차가 주차장에 들어오고, 나가게 되는지 알 수 있습니다.

이를 통해, 만약 주차장이 하나만 존재한다면 다음과 같은 방법으로 차들을 순서대로 보낼 수 있을 것입니다.

• 현재 차가 바로 빠져나갈 수 있다면 통과시킨다
• 현재 주차장에 있는 마지막 차가 빠져나갈 수 있다면 통과시킨다
• 둘 다 불가능하다면, 현재 차를 주차장에 넣는다

언제나 이 세 가지 중 하나는 수행해야만 차가 이동할 수 있고 이를 다 수행하여 주차장과 차고지에 차가 남지 않았다면, 결과는 항상 순서대로 통과했음을 알 수 있습니다. 만약 셋 다 불가능하다면, 더이상 차를 이동시키는 것이 불가능하다는 의미가 됩니다. 이러한 경우는 차가 주차장에서 빠져나가지 못하는 상황(주차장에 번호가 더 큰 차가 작은 차 뒤에 서서 막게 된 경우) 이므로, 순서대로 차를 빠져나가게 하지 못하는 상태가 되어, 불가능하게 됩니다.

주차장에 들어오는 차들은 항상 마지막에 들어온 차가 먼저 빠져나가기 때문에, 스택으로 관리해주면 어렵지 않게 구현이 가능합니다.

풀이

주차장이 하나만 있을 경우엔, 우리가 차를 주차장에 넣을 때, 어떤 주차장에 넣을지 고려해주지 않아도 상관이 없었습니다. 하지만 주차장이 여러개 있을 때에 차를 잘못된 주차장에 넣게 될 경우, 실제로는 가능한 경우임에도 순서대로 통과시키지 못할 수 있습니다.

예를 들어, 주차장이 2개 있고, 차가 3, 2, 4, 1번 순으로 들어오는 때에, 3번 차를 1번 주차장에, 2번 차를 2번 주차장에 넣고, 4번 차는 어떤 주차장에 들어가더라도, 차를 순서대로 정렬할 수 없게 됩니다.

하지만 3번 차와 2번차를 각각 1번 주차장에 넣게 되면, 4번 차를 2번 주차장에 넣은 이후, 1번차를 보내고 2, 3번 차를 1번 주차장에서, 4번 차를 2번 주차장에서 꺼내 보내는 것으로, 앞선 방법과 주차장에 다르게 넣게 된다면 순서대로 정렬할 수 있게 됩니다.

그렇다면, 차를 주차장에 넣어야 할 때, 어느 주차장으로 넣는 것이 좋을까요? 첫 차(번호 a)는 어떤 주차장에 넣어도 상관 없으므로, 두 번째 차(번호 b)를 고려하겠습니다. 만약 a가 b보다 작다면, b번 차를 a번 차가 있는 주차장에 넣을 수 없게 됩니다. 만약 나머지 모든 차들이 다 빠져나갔다 하더라도, b번 차는 a번 차가 나가지 않아서 통과할 수 없고, a번 차는 b번 차가 뒤를 막고 있어 빠져나갈 수 없기 때문입니다. 즉, 주차장에 들어갈 차는, 이미 들어가있는 차보다 더 번호가 작아야 한다는 것을 알 수 있습니다(혹은 비어있는 주차장에).

그렇다면, 주차장에는 현재 차보다 번호가 더 큰 차들이 존재하거나 비어있을 때, 어떤 주차장에 현재 차를 넣는것이 좋을까요? 편의상 현재 차 c보다 번호가 큰 a, b(a < b)번 차가 각각 주차장의 맨 뒤에 있다고 생각해보겠습니다. 이 때, c번 차는 항상 b보다 더 작은 a번 차 뒤에 놓는 것이 좋습니다.

만약 c번을 b번 차 뒤에 넣었을 때, 순서대로 차를 꺼내는 것이 가능하다 가정하고, 이를 (방법 1)이라 하겠습니다. 그렇다면, 각 주차장에는 a번과 c번이 들어가있고, 주차장에 차가 들어갔나 나오는걸 반복하다가, a번과 c번 또한 주차장에서 빠져나갈 것입니다. 다른 차들이 a번과 c번 주차장에 들어온다는 얘기는, 들어오는 차들이 각각 a번과 c번보다 더 작다는 것을 의미하게 됩니다. 이 때, c < a < b이기 때문에, 항상 c번이 a, b번보다 먼저 빠져나가게 되고, c번이 빠져나가면 주차장에는 c번이 들어오기 전인 a번과 b번이 각 주차장의 맨 뒤에 놓여있게 됩니다.

그렇다면, 똑같이 주차장에 들어왔다 나갈 때에, c번을 a번 뒤에 놓았다 가정해 생각해보겠습니다. 이 때에 각 주차장의 뒤에는 c번과 b번이 들어가있고, 앞서 c, a번 뒤에 들어올 차들은 모두 c, b번보다 번호가 작을 것이므로(c < a < b), 앞선 (방법 1)과 들어가는 주차장 번호만 서로 바뀐 상태로 똑같이 들어왔다 나갈 수 있게 됩니다. 이후 c번이 나가게 된다면, 나간 이후에 주차장에는 c번이 들어오기 전과 똑같은 상태의 a, b번이 남게 되므로, 이후엔 앞선 (방법 1)에서의 c번이 나간 이후를 그대로 반복하는 것으로 차들을 순서대로 보낼 수 있게 됩니다. 즉, c를 b번 뒤에 넣어 문제를 해결할 수 있다면, c를 a번 뒤에 넣는 것으로도 똑같이 문제를 해결할 수 있게 됩니다.

이를 남아있는 모든 주차장 쌍에 대해 생각해준다면, 순서대로 보내는 것이 가능한 모든 방법은, 현재 차량을 남아있는 넣을 수 있는 주차장들 중, 맨 뒤에 있는 차의 번호가 가장 작은 주차장 뒤에 넣은 것으로도(비어있는 주차장은 무한으로 가정) 항상 해결할 수 있음을 알 수 있습니다.

이를 관찰에서 다뤘던 내용과 합치게 되면

• 현재 차가 바로 빠져나갈 수 있다면 통과시킨다
• 현재 주차장에 있는 마지막 차들 중 한 차가 빠져나갈 수 있다면 통과시킨다
• 둘 다 불가능하다면, 현재 차를 자신보다 번호가 더 큰 차가 주차되어 있는 주차장 중, 가장 번호가 작은 차 뒤에 넣는다
• 번호가 더 큰 차가 없다면, 순서대로 통과시키는 것이 불가능하다

위 단계들을 순서대로 체크해주면 문제를 해결할 수 있게 됩니다. 이제 각 단계에서 소모되는 시간을 생각해보겠습니다.

1번 단계의 경우, 현재 나가야하는 번호와 차량을 비교해주면 되므로 O(1)에 가능합니다. 2번의 경우는 모든 주차장을 확인하도록 구현할 경우 O(M)이 되지만, 특정 번호의 차량이 주차장에 들어갈 때, 주차장에 들어갔는지 여부와 몇 번 주차장에 들어갔는지를 고려해주면 O(1)에 해결이 가능합니다. 4번의 경우, 3번을 실패했다면 불가능함을 출력하면 되므로 O(1)에 가능합니다.

이제 남은 단계는 3번 단계입니다. 어느 주차장에 넣을지 모든 주차장을 확인하는 것으로 구현한다면 O(M)에 문제를 해결할 수 있습니다.

결국, 시간복잡도에 가장 큰 영향을 주는 단계는 3번 단계이며, 우리는 모든 차에 대해서 위의 단계들을 수행해줘야 하므로, 총 O(NM)에 문제를 해결할 수 있게 됩니다.

번외 풀이 1

조금만 더 생각해보면, 3번 단계의 시간을 크게 줄일 수 있습니다. 주차장에 들어올 수 있는 차들의 번호는 1번부터 N번까지이므로, 이를 $\sqrt{N}$ 개씩 관리하여, 해당 구간 내에 있는 번호가 주차장 맨 뒤에 들어왔을 때, 이를 표시해주는 배열 A를 하나 만들어줍시다. 그렇게 되면, 우리가 현재 보고있는 차량 a가 들어가야 할 번호구간은 한 번에 $\sqrt{N}$개씩 건너띄며 찾아줄 수 있고, 그 이후 구간 중, 주차장 맨 뒤에 존재한다 표시된 구간에서만 $\sqrt{N}$개를 살펴봐 찾아줄 수 있어 $O(\sqrt{N})$에 해결 가능합니다. 이는 주차장에서 나갈 때에도 그 구간 내 $\sqrt{N}$개 모두 존재하지 않는지 확인해주면 되므로, 총 $O(\sqrt{N})$에 3번 단계를 모두 처리해줄 수 있어, 총 $O(N\sqrt{N})$에 문제를 해결할 수 있습니다.

번외 풀이 2

3번 단계를 균형이진탐색트리(Balanced Binary Search Tree)를 이용할 경우, N개의 원소에 대해서 수 a보다 큰 수들 중 가장 작은 수를 O(lgM)에 구할 수 있어, O(NlgM)에도 해결 가능합니다.

개미 - KOI 2014 지역본선 중등부 2번

관찰

가장 쉬운 방법은, 우리가 직접 매 초를 시뮬레이션 하면서 개미가 어느 방향으로 한 칸 이동하는지, 벽에 부딫혀서 어느 방향을 보게되는지를 매 순간 계산해주는 것입니다. 개미의 위치와 방향에 따라 다음에 이동하는 칸은 항상 정해져 있으므로 매 순간 직접 계산하면 총 O(t)의 시간에 문제를 해결할 수 있습니다.

개미는 벽에 부딪치기 전까지는 항상 가고있는 방향으로 매 초 이동합니다. 그렇다면, 개미가 가고있는 길로 100초 후에 벽에 부딪히게 된다면, 현재로부터 50초, 70초 후에도 항상 같은 방향으로 한 칸씩 이동할 것입니다.

즉, 우리는 몇 초 후에 벽에 부딪히는 지 계산할 수 있다면, 같은 방향으로 움직일 때 한 칸씩 움직이는 것이 아닌 ‘벽에 부딪칠 때까지 이동’시켜 주는 걸로 같은 방향으로 이동하는 경로를 한 번에 계산해줄 수 있습니다.

벽은 항상 x좌표가 0 혹은 w, y좌표가 0 혹은 h인 곳에 위치합니다. 이를 이용해 우리는 현재 보고 있는 방향으로 갈 때, 몇 초 후에 x, y 좌표가 벽에 닿는지 혹은 개미의 이동 시간이 끝나는지를 계산해 O(1)에 같은 방향으로의 모든 이동을 처리해줄 수 있습니다.

만약 공간이 크다면 이 방법은 그냥 시뮬레이션보다 더 빠르게 동작하지만, 이는 아직도 최악에 O(t) 만큼의 시간이 걸릴 수 있습니다. x 혹은 y좌표가 최대 1이라면, 항상 매 초마다 개미는 벽에 부딪히게 되므로, 최악의 경우엔 그냥 시뮬레이션을 할 때와 크게 다를 바 없게 됩니다.

개미가 a초동안 이동하고나서, 처음의 위치로 다시 돌아와 처음과 같은 곳을 바라보게 됐다면, 2a초가 지나고 나면 개미는 어디에 있을까요? 그럼 10000a초가 지나고 나면 어느 위치로 돌아오게 될까요?

처음과 같은 위치에서 같은 곳을 바라보고 있다면, 개미는 항상 처음에 이동했던 경로와 같은 경로로 계속 이동하게 될 것이므로, a초가 지나 처음 위치의 같은 방향을 보고 있게 된다면, 2a초든, 10000a초든, 항상 a의 배수인 시간이 지난다면 똑같이 처음 위치에 존재하게 될 것입니다.

이를 이용해, 직접 시뮬레이션을 하여 처음으로 a초 후에 처음 위치에서 같은 방향을 보게 되는 시간이 지난다면, 우리는 a의 배수만큼의 시간엔 항상 처음 위치와 같은 곳을 보게 된다는 것을 알 수 있으므로, t를 a로 나눈 나머지 만큼의 시간에 대해서만 시뮬레이션하면 최종 위치를 구해줄 수 있게 됩니다. 결국, 우리는 한 번 첫 위치로 오기까지의 사이클에 해당하는 시간만큼만 시뮬레이션 해주면 되므로, 시간복잡도는 O(사이클의 길이) (혹은 O(a))가 됩니다.

그렇다면, 사이클의 길이는 얼마나 될까요? 아쉽지만, w와 h 모두 소수인 경우, 사이클의 길이는 최대 2wh 까지 될 수 있으므로, 시간복잡도는 최악에 O(wh)가 됩니다. 만약 공간이 작고 t가 크다면 이 시간으로 충분히 해결 가능하지만, 공간 또한 큰 경우 이 방법은 오랜 시간이 걸리게 됩니다.

풀이

만약 개미가 2차원에 존재하지 않고, 1차원에 존재한다면 어떻게 될까요? x축으로 w 길이만큼의 선이 존재한다고 하면, t초 후에 개미의 위치는 어떻게 알 수 있을까요?

앞서 우리가 사이클의 길이를 구한 것처럼, 1차원 개미에 대해서도 사이클의 길이 a를 구할 수 있을까요? 만약 4의 길이인 선에서 1인 위치에 개미가 오른쪽을 보고있다면, 개미는 몇 초 후에 다시 처음 위치에서 같은 방향을 볼 수 있을까요?

이는 어렵지 않게 구할 수 있습니다. 위치 1의 개미는 오른쪽으로 3, 왼쪽으로 4만큼 이동 후, 오른쪽으로 1만큼 이동했을 때 위치 1에서 오른쪽을 보게 될 것이므로, 8초를 기준으로 사이클을 가지게 됩니다.

실제로 해보면 개미의 위치에도 상관없고, 보는 방향에도 상관없이 항상 최소 사이클이 8이라는 사실을 어렵지 않게 알 수 있으며, 항상 2w가 된다는 것을 쉽게 보일 수 있습니다. 개미가 벽에 부딪히면 반대 방향으로 이동하는 것을, 길이가 2배인 선을 계속 걸어가는 것으로 생각하면 개미는 항상 같은 방향으로 걸어가는 것으로 볼 수 있으므로, 사이클의 길이는 항상 2w가 되어 우리는 어렵지 않게 사이클을 알 수 있습니다.

그렇다면 1차원에 y축만 존재할 경우엔 어떻게 될까요? 이는 x축을 그대로 회전시킨 것과 다름 없기 때문에 똑같이 2h가 사이클이 됩니다.

우리는 2차원에 있는 개미를 1차원으로 옮겼을 때, 각각 2w, 2h의 사이클을 가지고 움직인다는 사실을 알 수 있었습니다. 그렇다면, 혹시 이 정보를 이용해 2차원 개미도 쉽게 해결할 수 있을까요?

한 번, 2차원의 개미를 x축의 간격을 굉장히 좁혀보고, 한 번 y축 또한 좁혀보도록 하겠습니다.

2차원 개미의 움직임을 x축을 굉장히 좁혀 y축의 움직임만 보거나, y축을 굉장히 좁혀 x축의 움직임만 보면 어떻게 될까요? 아마 각각 y축, x축을 움직이는 1차원의 개미가 보일 것입니다.

개미가 왼쪽, 오른쪽의 벽에 부딪히면 90도로 방향을 틀어 각각 오른쪽, 왼쪽으로 이동하므로, x축 위에 있는 벽을 부딫히면, x축의 이동방향이 정 반대로 바뀌게 됩니다. 마찬가지로 위, 아래 벽에 부딫히면, 각각 아래, 위로 이동하므로 y축 위에 있는 벽을 부딪히면 y축의 이동방향이 정 반대로 바뀌게 됩니다.

즉, 2차원에 있는 개미는 x, y축이 서로에게 영향을 주지 않고, 서로 다른 1차원의 움직임이 합쳐진 것과 같다는 것을 알 수 있습니다.

결국 각 축의 좌표는 서로에 영향을 주지 않고 독립적으로 바뀌게 되므로, 우리는 사이클을 구하는 과정을 2차원에서 생각하는 것이 아닌, 각 x, y축으로 나누어 구할 수 있고, 각각 사이클은 2w, 2h가 됩니다. 이를 이용해 우리는 최종 x축의 위치를 t를 2w로 나눈 나머지를 시뮬레이션 해서 구해줄 수 있으며, y축 또한 마찬가지로 2h로 나눈 나머지 시간만큼 시뮬레이션 하면 쉽게 구해줄 수 있습니다.

이를 이용해 우리는 O(w + h)에 문제를 해결할 수 있습니다. 또한, 2w, 2h로 나눈 나머지 시간만큼에 대해, 개미는 벽을 최대 3번만 부딫히게 되므로 이를 이용해 벽에 부딪힐 때까지의 이동을 O(1)에 계산해준다면, 총 6번만에 개미의 최종 위치를 구할 수 있어 O(1)로 해결할 수도 있습니다.

Black Chain - ICPC Seoul Nationalwide Internet Competition 2018 A번

관찰

만약 우리가 무게의 총 합이 n이 되는 $a_{1}, …, a_{k}g$짜리 독립된 고리들을 만들고 싶다면, 한 번 푸는 걸로 $a_{1}$을, 또 한 번 푸는 걸로 $a_{2}$를 만들 수 있고, 이처럼 점점 하나씩 풀어가다가, $a_{(k-1)}g$짜리 고리를 만들기 위해 풀고나면, 나머지는 $a_{k}g$ 짜리가 되므로, 총 k - 1번만 풀어도 k개의 고리들을 만들 수 있습니다. 이를 통해, 우리는 순서에 상관없이, (최종적으로 남아있는 풀어진 고리들의 수 - 1)이 구하고자하는 횟수임을 알 수 있습니다.

풀이

이제 우리는 만드는 순서는 상관없으므로, N개의 고리들을 이용해 다 만든 이후, 남아있는 수만 알아도 답을 구할 수 있다는 것을 알게 되었습니다. 그렇다면, 이를 위해 가장 작은 무게부터 하나씩 만들어보도록 하겠습니다.

1g짜리 고리는, 어떠한 조합으로도 만들 수 없고, 단일고리 하나가 무조건 존재해야합니다. 그러므로 n이 1이 아닌 경우, 적어도 하나의 1g 고리를 만들어야합니다.

2g 고리의 경우, 1g과 n-1g의 고리가 있다면, n-1이 2 이하가 아닌 경우 무조건 하나 만들어야함을 알 수 있습니다.

그렇다면, 3g은 어떻게 될까요? 이 때, 남아있는 고리는 1, 2, n-3g이기 때문에, 항상 1, 2g을 조합하여 3g을 만들 수 있고, 더 만들 필요가 없습니다.

4g을 확인하면 앞선 3g과 같이 1, 2, n-3g이 남아있습니다. 우리는 1, 2g을 이용해 1 ~ 3g을 모두 만들 수 있기 때문에, n-3이 4g이하라면 만드는 것이 가능하지만, 아닐 경우 1 ~ 4g 하나를 만들어야 한다는 것을 알 수 있습니다.

만약, 우리가 1, 2, 4g짜리 고리를 만들게 되면, 그 이후엔 1, 2, 4g을 이용해 1 ~ 7g까지의 모든 조합을 만들 수 있게 됩니다. 더 이상 만들 수 없는 경우는, 나머지 고리가 8g 초과일 때가 되므로, 1 ~ 8g을 추가해야 할 것입니다.

규칙을 보신다면, 아마 고리를 2배씩 늘리면서, 필요한 고리 중 가장 최대의 길이로 잘라내야한다는 것을 알 수 있을 것입니다. 그렇다면 실제로 맞는 방법인지 증명해봅시다.

a1, a2, …, ak g의 고리를 이용해, 1 ~ p g(p = a1 + … + ak)까지 모든 조합을 만들 수 있다고 합시다. 이 때, 우리는 남아있는 고리가 p + 1g 초과일 경우, 항상 p + 1g을 만들어 낼 수 없기 때문에, 1 ~ p + 1g 짜리 고리를 만들어야하고, 남아있는 고리는 항상 이보다 길이가 크기 때문에 언제나 만들어 낼 수 있습니다.

이 때, p + 1g짜리 고리를 만든다면, 1 ~ p g, p + 1 ~ 2p + 1 = 1 ~ 2p + 1 g을 모두 만들 수 있는데 반해, 1 ~ p g짜리 고리를 만들면 최대 1 ~ 2 * p g만 만들 수 있게 되므로, 최대한 많은 경우의 수를 만들기 위해선, 1 ~ p g짜리를 만들 때, 이를 p + 1g짜리 고리를 만드는 것으로 대체해도 상관 없게 됩니다. 만약에 p + 1g짜리 고리를 만들 수 있다면, 남아있는 고리가 p g 이하라는 것이므로, 어차피 모든 경우를 만들 수 있게 되어, 우리는 매 순간, 만들 수 있는 가장 큰 고리를 만드는 것이 항상 좋은 답을 만든다는 것을 알 수 있습니다.

이를 1g부터 계속 반복해나가면, 우리는 항상 2의 거듭제곱 꼴의 고리들이 필요하고, 남아있는 고리가 필요한 고리보다 더 작거나 같아질 경우까지 만들면, 언제나 원하는 무게를 만들어낼 수 있게 됩니다.

그리고, 우리는 이를 1g이 무조건 필요하다는 것을 증명했고, 이후에 만들어지는 고리들은, 존재하지 않으면 답을 만들어낼 수 없는 고리들 중, 가장 길이가 긴 고리들을 이용해 만들었기 때문에, 이보다 더 짧은 고리들을 쓴다면 항상 우리가 구한 답보다 더 크거나 같다는 것을 알 수 있습니다. 즉, 다른 방법으로도 답을 만들 수 있다면, 그 고리들에서 합치거나 길이를 길게 나누는 것으로 항상 우리가 만들어낸 답과 같은 형태를 만들 수 있어, 이 방법으로 구한 것이 항상 답이 된다는 것을 알 수 있습니다.

이는 고리의 크기를 2배씩 늘리면서, 주어진 n보다 클 때까지만 확인하면 되기 때문에, 총 O(lgN)에 문제를 해결할 수 있습니다.

코드

짐 정리

#include <bits/stdc++.h>
using namespace std;

int n, min1, res;
int arr[10010], tarr[10010], visit[10010], table[100010];

int main(){
	int i, now, nmin, r, cnt;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) scanf("%d", &arr[i]), tarr[i] = arr[i];
	sort(tarr + 1, tarr + n + 1);
	min1 = tarr[1];
	for(i = 1; i <= n; i++) table[tarr[i]] = i;
	for(i = 1; i <= n; i++){
		if(visit[i] || table[arr[i]] == i) continue;
		now = i;
		cnt = 0;
		r = 0;
		nmin = arr[i];
		while(!visit[now]){
			visit[now] = 1;
			r += arr[now];
			nmin = min(nmin, arr[now]);
			now = table[arr[now]];
			cnt++;
		}
		res += r;
		res += min((cnt - 2) * nmin, (cnt + 1) * min1 + nmin);
	}
	printf("%d", res);
	return 0;
}

개미

#include <bits/stdc++.h>
using namespace std;

int n, m, tt, a, b, t;

int main(){
    int temp;
    scanf("%d %d %d %d %d", &n, &m, &a, &b, &t); tt=t;
    temp = min(t, n - a); a = a + temp; t -= temp;
    t = t % (2 * n); temp = min(t, n); a -= min(t, n); t -= temp; a += t; t = tt;
    temp = min(t, m - b); b = b + temp; t -= temp;
    t = t % (2 * m); temp = min(t, m); b -= min(t, m); t -= temp; b += t;
    printf("%d %d", a, b);
    return 0;
}

Black Chain

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, sum = 7, addsum = 4;

int main(){
	int i, cnt = 1;
	scanf("%lld", &n);
	if(n == 1){ printf("0"); return 0; }
	while(true){
		if(n <= sum) break;
		sum += addsum; sum += sum + 1; addsum *= 2;
		cnt++;
	}
	printf("%d", cnt);
	return 0;
}