알고리즘 문제 접근 과정 10
알고리즘 문제 접근 과정 10
이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다.
최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다.
Musical Notes - USACO December 2009 Contest Silver 2번
문제가 영어로 되어있어서, 동일한 문제 상황의 번역을 첨부하겠습니다.
문제
카이홀에서는 한창 카이스트 합창 동아리 ‘코러스’의 콘서트가 진행되고 있다. 이번 콘서트에는 총 N개의 곡이 1번부터 순서대로 진행되며, 각 i번 곡은 Ai 만큼의 시간동안 진행되며, 끝나는 동시에 바로 다음곡이 진행되는 형태로 이루어진다(첫 곡은 0분부터 시작한다).
많은 사람들이 미리 도착하여 앉아 콘서트를 보고 있었지만, 그 중 일부 M명의 사람들은 부득이하게 지각하게 되어, 각 i번 사람마다 콘서트가 시작한 후 Bi 만큼의 시간 이후에 도착하게 된다.
하지만 모든 사람들은 이미 문자로 공연 진행 순서를 받았기 때문에, 각 곡이 몇 분만에 끝나는지에 대한 내용을 받았고, 이를 통해 자신이 몇 번 곡이 진행될 때 도착했는지를 알아내고 싶어한다.
하지만 이들은 콘서트에 더 이상 늦지 않기위해 열심히 달려가는 중이라 이를 확인할 수가 없어, 이를 알 수 있는 리스트 작성을 부탁했다. 각 지각하는 사람들이 몇 번 곡이 진행될 때 도착하는지에 대한 정보를 알려주자! (특정 시간에 한 곡의 시작과 끝이 동시에 존재한다면, 시작하는 곡을 들으며 입장하게 된다)
입력
첫 줄에 곡의 수 N(1 <= N <= 50,000)과 사람의 수 M(1 <= M <= 50,000)이 주어진다. 둘째 줄에 각 곡의 길이 Ai(1 <= Ai <= 10,000)가 순서대로 주어진다. 셋째 줄에 각 사람의 도착 시간 Bi가 순서대로 주어진다.
출력
각 사람이 도착할 때에 진행되는 곡의 번호를 순서대로 출력한다.
관찰
가장 쉬운 방법으로는 콘서트의 연주 리스트가 주어질 때, 각 지각하는 사람마다 1번부터 N번 곡까지에대해 순서대로 보면서 현재 곡이 연주될 때에 들어오는지 확인하는 방법이 있습니다. i번 곡이 연주되는 순간은, (1 ~ i-1번 곡의 연주가 끝나는 시간)부터 i번 곡의 길이만큼 연주되기 때문에, 1번부터 순서대로 N번 곡까지 보게 된다면, 어떤 곡이 언제 시작해서 언제 끝나는지를 알아낼 수 있습니다. 이를 마치고 나면, M명의 모든 사람들마다 N개의 곡 중 어떤 곡이 연주되는지 각 곡이 연주되는 시간과 비교하는 것으로 알아낼 수 있기 때문에, O(NM)의 시간복잡도로 문제를 해결할 수 있습니다.
그렇다면, 이 때에 우리가 알게 된 N개의 곡들이 각각 연주되는 구간을 보면 어떻게 될까요? 어떤 i에 대해, i번 곡의 구간이 i + 1번 곡의 구간보다 더 뒤에 있거나 겹치는 경우가 존재할 수 있을까요? 이런 경우는 절대 존재할 수 없습니다. i번 곡이 끝나는 구간은 항상 i + 1번 구간의 시작이 되기 때문에, 항상 i번 곡의 구간은 i + 1번 곡의 구간보다 더 앞서서 있게 되고, 결국 우리는 1번부터 순서대로 존재한다는 것을 알 수 있습니다.
풀이 1
주어진 곡들의 연주 시간이 항상 1번부터 N번부터 순서대로 진행된다는 것을 알고 있는 상황에서, i번 사람이 들어올 때 연주되는 곡을 빠르게 알 수 있는 방법이 있을까요? 만약 N/2번 곡이 i번 사람이 들어올 때보다 더 늦게 연주가 된다면, 이후의 곡들 또한 더 늦게 연주가 될 것이기 때문에, i번 사람은 항상 1~N/2 - 1번 곡들 중 한 곡이 연주될 때에 도착한다는 것을 알 수 있습니다. 반대의 경우도 후보로 N/2 + 1 ~ N번 곡들만 남기 때문에, 우리가 N/2번이라는 하나의 곡을 확인하는 것만으로 답의 후보를 절반으로 줄일 수 있었습니다. 그렇다면 이를 계속 반복하여 남은 후보 중 가운데 곡과 비교해주면 어떻게 될까요? 우리가 선택한 곡이 더 늦게 연주되든, 혹은 이미 연주되었든, 남은 답의 후보는 항상 절반으로 줄어든다는 것을 알 수 있습니다.
이를 반복해서 매 순간 한 번의 비교로 후보를 계속 반씩 줄여나갈 수 있고, 우리는 한 명의 사람에 대해 항상 아무리 많아도 logN + 1번의 질문만으로 답을 구해낼 수 있게 됩니다. 지각한 사람은 총 M명이 있기 때문에, 이 경우 시간복잡도는 O(MlogN)이 됩니다.
풀이 2
이분탐색을 이용한 방법 또한 굉장히 빠른 방법이지만, 더 빠르게 답을 구하기 위해서 우리는 다른 방법을 생각해볼 필요가 있습니다.
우리가 관찰에서 가장 먼저 풀었던 방법보다, 더 쉽게 풀 수 있는 방법이 있을까요? 바로 ‘모든 시간을 직접 시뮬레이션 해보기’ 입니다.
관찰에서 생각했던 것처럼, N개의 곡들에 대해 각 곡이 어느 시간대에 연주되는지 알고 있다면, 우리는 1번부터 N번 곡이 순서대로 진행된다는 것을 알고 있으므로, 처음 1번 곡부터 현재 곡이 끝날 때마다, 다음 곡은 2번, 3번과 같은 순서로 진행됨을 알 수 있습니다.
우리는 현재 시간 i에 대해 연주되는 곡을 알고 있다면, 시간 i에 도착하는 사람들은 항상 그 곡을 들으며 입장할 것이란 것을 알 수 있습니다. 이를 단순하게 매 시간마다 모든 사람들에 대해 도착 여부를 판단해주면, O(콘서트 시간 * M)에 문제를 해결할 수 있습니다.
만약 이 상태에서, 사람들이 무작위의 시간으로 입장하는 것이 아닌, 먼저 입장하는 사람부터 나중에 입장하는 사람들까지 순서대로 들어온다면 어떨까요? 다시 말해, 만약 우리가 입력으로 받은 사람들을 지각한 시간 순서대로 정렬한다면 어떻게 될까요?
그리고 여기에 우리가 앞서 발견한 간단한 성질을 그대로 적용시키면, 시간을 획기적으로 바꿀 수 있습니다. 우리는 곡이 1번부터 N번 곡까지 순서대로 진행됐던 것처럼, 사람들도 1번부터 M번 사람까지 순서대로(혹은 같이) 들어온다는 것을 알고 있습니다. 즉, 1번 사람이 도착하지 않았다면, 2번 사람도 도착하지 않았을 것이고, 같이 들어오는 사람들이 있을 수 있다고 해도, 가장 처음에 도착할 사람은 1번 사람이라는 것은 변함이 없습니다.
즉, 우리는 현재 시간에 연주되는 곡을 찾고 나면, 1번 사람부터 시작해 순서대로 보면서, 현재 사람이 콘서트에 입장하는지 확인해주면 됩니다. 이 때, j번 사람이 마지막으로 들어오고 났다면, 그 다음 시간에 1~j번 사람들은 이미 입장했으므로, j + 1번 사람부터 확인하는 것으로 이어나갈 수 있습니다.
각 시간에 확인하는 사람의 수는 (현재 시간에 입장하는 사람 수 + 1)명만 보게 되므로, 우리는 총 O(M + 콘서트 시간)에 문제를 풀 수 있게 됩니다.
우리는 앞선 방법을 조금 보완하는 것만으로 시간복잡도에서 콘서트 시간을 고려하지 않을 수 있게 됩니다. 다음과 같은 상황을 생각해보겠습니다.
- 1번 곡은 0~150 동안 진행되고, 사람은 1, 149의 시간에 지각하는 경우
이 때, 시간 1에 1번 사람이 지각했다는 것을 확인하고 나면, 우리는 매 시간 1을 늘려 확인을 하고 있습니다. 하지만 실제로는 곡도 시간 150까지 진행되고, 2번 사람은 시간 149에 도착하기 때문에 2~148까지의 시간엔 아무것도 하지 않는 것이 됩니다. 그렇다면, 어떤 일이 벌어지는 경우를 생각해봅시다. 시간이 지나서 변화가 생기는 일은
- 곡이 다음 곡으로 바뀌거나
- 지각한 사람이 도착하는 경우
의 두 가지가 있습니다. 즉, 이 두 가지 일이 일어나지 않는 시간들은 생략해도 문제가 없게 됩니다. 이제 위 두 가지가 일어나는 때를 확인해보겠습니다.
1번 경우가 일어나는 일은, 항상 현재 곡이 끝나는 시간이 됩니다. 2번 경우가 일어나는 일은, 항상 다음 사람이 도착하는 시간이 됩니다.
즉, 우리는 매 순간마다 1번 일, 혹은 2번 일이 일어나는 경우만이 존재하므로, 둘 중 더 먼저 일어나는 시간에 대해서만 처리해주는 것으로 실제 고려해야 하는 시간들을 모두 고려하여 줄 수 있습니다.
결국 매 순간, 가장 시간이 앞선 사람과 곡에 대해, 사람이 먼저 도착할 경우, 그 사람은 현재 곡을 듣는 상태로 입장한다는 것을 기록한 후 다음 사람으로 넘어가고, 곡이 먼저 끝날 경우 다음 곡으로 넘어가는 것을 반복하여 모든 사람에 대해 기록을 마치면 우리는 구하고자 하는 답과 완전히 일치하게 시뮬레이션을 진행할 수 있습니다.
결국 우리는 매 시간마다 사람과 곡을 각각 한 개씩 확인 하기 때문에, 존재할 수 있는 유의미한 시간의 총 수인 O(N + M)에 문제를 해결하여, 이분탐색보다도 더 빠르게 문제를 해결할 수 있습니다.
매 순간 필요한 정보는 가장 앞에 있는 원소이기 때문에, 연주되는 곡과 지각하는 사람에 대한 두 개의 큐를 이용하여, 먼저 일어나는 순서대로 넣어 관리하는 것으로 어렵지 않게 구현할 수 있습니다.
다만 이 경우에, 우리는 맨 처음 주어진 사람들을 입장하는 순서대로 정렬하는 과정이 필요합니다. 즉, 정렬하는 과정에서 일단 O(MlgM)의 시간이 필요하게 되어, 문제를 해결하는 단계가 이분탐색보다도 더 빠르기는 하나, 전체 시간복잡도 자체는 동일하게 됩니다.
그러나, 이러한 방법으로 두 개의 큐를 가지고 투 포인터 방법으로 문제를 해결하는 방법은 굉장히 중요합니다. 만약 입력이 정렬된 순서로 제공된다면 이 둘은 큰 시간복잡도 차이를 가지게 되며, 몇몇 문제들은 이러한 투 포인터 개념을 문제에 적용시키는 것을 원하는 경우가 많습니다. 그러므로 이 두 가지 방법을 모두 기억해두시면 큰 도움이 될 겁니다.
곱셈
관찰
어떤 수 A를 C로 나눈 몫을 p, C로 나눈 나머지를 r이라고 하면, 우리는 A를
- A = p * C + r
과 같이 나타낼 수 있습니다. 이처럼 A를 C로 나눈 몫과 나머지가 p, r이라고 할 때, A * A를 C로 나눈 몫과 나머지는 어떻게 될까요? 실제 계산해보면
- A * A = (p * C + r) * (p * C + r) = (Cp^2 + 2pr)C + r^2
이 된다. 이 때, (Cp^2 + 2pr) * C는 C로 나눈 나머지가 0이기 때문에, 실제로 남은 나머지는 r^2을 C로 나눈 나머지가 될 것입니다.
이처럼 C로 나눈 나머지가 0인 항은 다른 무슨 수와 곱해도 C로 나눈 나머지가 0이 되기 때문에, 우리는 몫을 고려하지 않고, 항상 A를 C로 나눈 나머지 r만 가지고 연산을 해도 문제가 되지 않습니다.
즉, A^3은 r^3을 C로 나눈 나머지와 같고, 이는 (((r * r을 C로 나눈 나머지) * r)을 C로 나눈 나머지) 와 같이 표현이 가능하여, 우리는 최종 수가 아무리 크다 하더라도, 중간에 곱해진 값들의 나머지들만 이용해서 계속 곱해나가더라도, 우리가 구하고자 하는 나머지 값과 항상 같아진다는 것을 알 수 있습니다.
이를 이용해 가장 쉽게 생각할 수 있는 방법은, A를 B번 곱해나가면서, 매 번 A, A^2, A^3, … 과 같이 A가 한 번 곱해질 때마다 C로 나눈 나머지 값을 저장해나가는 것입니다. 이렇게 할 경우 우리는 A^B이 얼마나 크든 상관없이 C로 나눈 나머지가 정수형 범위를 넘지 않는 다는 것을 이용해 답을 구해줄 수 있습니다. 이 경우 우리는 곱해주는 횟수만이 중요해지므로, O(B)에 문제를 해결할 수 있습니다.
하지만 주어진 B 자체도 굉장히 크기 때문에, 우리가 아무리 O(B)로 문제를 풀어도 시간은 굉장히 부족합니다.
풀이
이 문제를 풀기 위해 앞서 관찰에서 발견했던 성질을 생각해봅시다. 우리는 A^B을 구하기 위해서, A^(B-1)을 C로 나눈 나머지와, A를 C로 나눈 나머지를 곱하고, 그 값을 다시 C로 나눈 나머지를 구함으로 답을 구했습니다. 이 때 우리는 어떤 두 수의 곱의 나머지는, 각 수의 나머지의 곱의 나머지를 구하는 것으로 해결이 가능했습니다.
그렇다면, A^B을 A와 A^(B - 1) 말고, 더 좋게 쪼개서 답을 구할 수 있지 않을까요?
B가 짝수일 때를 생각해봅시다. 이 경우, 만약 우리가 A^(B/2)의 값을 알 수 있다면, 우리는
- A^B = A^(B / 2) * A^(B / 2)
로 나타낼 수 있게 됩니다. 즉, 이를 최대한 절반씩 줄여나갈 수 있다면, A^(B / 2)를 구하기 위해서 A^(B / 4)를, A^(B / 8)을, 이를 반복하면 우린 약 lg B 개 정도의 값에 대해서만 알면 문제를 해결할 수 있다는 것을 알 수 있습니다.
홀수일 경우
- A^B = A^((B - 1) / 2) * A^((B - 1) / 2) * A
와 같이 만드는 것으로 짝수를 만들어 낼 수 있으므로, 우리는 모든 수에 대해 항상 절반씩 나누어나갈 수 있게됩니다.
함수 F를 다음과 같이 정의해봅시다.
- F(B) = (A^B를 C로 나눈 나머지)
그럴 경우, F를 어떻게 정의하면 될까요?
가장 작은 경우인 B가 1일 때에, A를 C로 나눈 나머지를 반환해주고, 나머지 경우엔 앞서 우리가 발견한 식을 이용해 구해보도록 합시다.
- F(B) = F(B / 2) * F(B / 2) % C (B가 짝수) = F(B / 2) * F(B / 2) % C * A % C (B가 홀수) = A % C (B가 1)
이제 우리는 실제 F(B)를 구해주기만 하면 이 것이 답이 됨을 알 수 있습니다. 그렇다면 시간복잡도는 어떻게 될까요? 절반씩 나누었기 때문에 O(lg B)가 될까요?
사실 아직은 그대로 O(B)가 됩니다. 이를 알아보기 위해서는 각 F(B)가 어떻게 호출되는지 볼 필요가 있습니다.
예를 들어 F(8)이 호출되었다고 할 때, 각 F가 호출되는 그림을 그려봅시다.
결국, 매 높이마다 F는 2^(높이) 만큼 호출이 되기 때문에, 총 O(B)만큼의 함수가 호출되어, 아직도 시간복잡도는 변함이 없게 됩니다.
그렇다면, 앞서 배웠던 방법대로 메모이제이션을 쓰면 어떻게 될까요? 물론 메모이제이션을 쓰면 시간복잡도는 걱정하지 않아도 됩니다. 하지만 이 문제에서 B는 32bit 정수형 범위까지 가능하기 때문에, 이를 모두 기록할 수 있는 배열을 만드는 것은 어려운 일입니다.
즉, 우리는 그냥 시도해서는 메모이제이션을 쓰는 것 자체가 불가능하게 됩니다. 그렇다면, 어떻게 해야 시간복잡도를 줄일 수 있을까요?
1) 작은 범위만 메모이제이션
쉬운 방법으로는 메모이제이션을 ‘작은 범위에만 쓰는 것’으로 시간복잡도를 줄이는 것입니다. B의 범위까지의 모든 값들을 저장하는 배열을 만들 수는 없으므로, 약 100만(2^20)까지에 해당하는 값들만 메모이제이션을 한다고 합시다.
그렇게 될 경우, F(B)에서, B가 100만 이하일 경우 메모이제이션을 통해 호출을 크게 줄여줄 수 있게 됩니다. 이 때, 우리가 앞서 그린 그림을 보게 되면, B가 작아질 수록 호출하는 횟수가 2배씩 늘어간다는 것을 볼 수 있습니다. 허나 이제 100만 이하인 수는 딱 한 번씩만 보게 되기 때문에, 우리가 그린 그림에서 아래에서 20개까지의 높이는 없는 것처럼 볼 수 있게 됩니다.
결국 그림에서 높이가 20만큼 줄어든 것과 같은 효과를 볼 수 있어, 우리가 보는 함수의 수는 B / 100만 개가 되어 시간을 크게 줄일 수 있게 됩니다. (O(B / 100만) = O(B) 이지만, 계수가 매우 크게 줄어드므로 동작속도가 빨라집니다)
2) 실제 사용되는 값들만 메모이제이션
사실 우리가 F의 인자로 주게 되는 값들은 아무리 많아도 lgB + 2개를 넘지 않습니다. 즉, 우리는 몇백만, 몇억 정도 크기의 배열을 만들어도 실제 사용되는 값을 100개도 채 되지 않습니다. 그렇다면, 이처럼 배열을 만들어 메모이제이션 하는 것이 아니라, 실제 사용할 값들만 메모이제이션 하면 어떻게 될까요?
0번 배열에는 F(B)의 값이, 1번 배열에는 F(B / 2), 2번 배열에는 F(B / 4), …, 이를 반복해 약 lg B개의 배열에 값을 다 담고 나면, 우리는 어떤 값이 실제 기록이 되었는지 여부를 0번부터 lg B + 2까지의 값들만을 찾아보는 것으로 알 수 있게 됩니다. 이전처럼 한 번에 기록 여부를 판단할 수는 없지만, 100개도 채 되지 않는 수를 찾아보는 것은 크게 어렵지 않는 일이 됩니다.
결국 우리는 기록을 lg B 만에 찾는 메모이제이션을 쓴 것과 다름없게 되므로, 총 시간복잡도는 O(lg^2 B)가 되어 굉장히 빠르게 답을 찾을 수 있게 됩니다. (실제 기록되는 값들은 굉장히 적기 때문에, 메모이제이션을 해싱을 쓰는 방법을 사용하면 약 O(lg B)에도 문제를 해결할 수 있게 됩니다.)
3) 식을 조금만 변형하기
실은 우리가 식은 조금만 변형해서 앞서 고려한 것들을 이용하지 않고도 O(lg B)를 만들어낼 수 있습니다. 아까 우리가 만든 식을 다시 가지고 옵시다.
- F(B) = F(B / 2) * F(B / 2) % C (B가 짝수) = F(B / 2) * F(B / 2) % C * A % C (B가 홀수) = A % C (B가 1)
여기에서 시간복잡도에 많은 부분이 들었던 이유는 바로 F(B / 2)가 두 번 호출된다는 것이었습니다. 결국 이는 매 단계에서 함수의 호출을 2배씩 늘려 O(B)의 시간복잡도를 만들어 냈습니다.
그렇다면, 우리가 F(B)가 호출 되었을 때, F(B / 2)의 값을 T라는 변수에 기록을 하면 어떻게 될까요?(B가 1이 아닌 경우)
- F(B) = T * T % C (B가 짝수) = T * T % C * A % C (B가 홀수) = A % C (B가 1)
이 때, T는 현재의 B에 대해 값이 변할리가 없기 때문에, 식에 나와있는 T, A, C 모두 상수가 됩니다. 즉, 우리는 F(B / 2)를 한 번만 호출하고도 남은 식들을 O(1)에 계산해줄 수 있게 됩니다.
그렇다면, T를 구하기 위해 호출되는 F(B)들을 그림으로 그리면 어떻게 될까요?
매 순간 F(B), F(B / 2), F(B / 4), …, F(1)까지의 모든 값들이 한 번 씩만 호출되기 때문에 총 호출되는 함수의 수는 lg B + 2를 넘지 않습니다. 그리고 나머지 모든 연산은 상수이기 때문에, 우리는 총 O(lg B)에 문제를 해결할 수 있습니다.
달팽이는 올라가고 싶다 - COCI 2010/2011 Contest 2 1번
관찰
달팽이는 낮 동안은 나무에 올라갔다가, 밤에는 나무에서 미끄러져 내려오게 된다는 조건이 있지만, 나무에 다 오르고 나면 더 이상 내려오지 않게 된다는 추가 조건으로 인해 어려움이 생깁니다. 만약 하루씩 기준으로 잡고 달팽이가 나무를 오른다 생각하면, 항상 낮에는 A만큼, 밤에는 B만큼 내려오므로 A - B씩 오른다 생각할 수 있었지만, 낮 동안 나무에 오르고 나면 B만큼 더이상 내려오지 않으므로, 매일 A - B씩 오른다는 방법으로 계산을 하기 어려워집니다.
그렇다면, 어떻게 이 문제를 해결할 수 있을까요?
가장 쉬운 방법으론 우리가 실제 달팽이가 나무를 오르는 과정을, 낮과 밤을 나누어 실제로 시뮬레이션하는 방법이 있습니다. 항상 낮에는 A만큼 오르고, 밤에는 B만큼 내려오므로, 첫째날 낮, 밤, 둘째날 낮, 밤 과 같이 하루하루 오르고 내려가는 일을 직접 구해준다면, 어느날 나무를 모두 오르게 되는지 알 수 있습니다.
하지만 이 방법으론 문제를 빠르게 해결하기 어려울 수 있습니다. 우리는 매일매일의 낮과 밤을 모두 계산해줘야하기 때문에, 우리는 ‘나무에 오르는 일수’ 만큼의 연산을 하게 됩니다. 이 때 만약 달팽이가 굉장히 오랜 시간 후에야 나무에 오르게 된다면? 우리의 방법으로도 오랜 시간 후에야 나무 꼭대기에 언제 도착하는지 알 수 있게 됩니다.
풀이
조금만 더 생각해보면, 문제를 조금 바꾸어 생각하는 것으로, 우리가 처음 생각한 아이디어를 적용시킬 수 있습니다.
처음에 우린 하루동안 달팽이가 A씩 오르고 B씩 내려가기 때문에, A - B씩 오른다 생각했지만, 낮 동안에 모두 오르면 밤에 떨어지지 않기 때문에 이 방법을 사용하기 어려웠습니다.
여기서 주목할 점은, ‘낮 동안에 모두 오르면 밤에 떨어지지 않는다’를 살펴보면, ‘낮 동안에 모두 오르지 않는다면, 밤에 떨어지게 된다’ 가 된다는 점입니다. 즉, 우리는 나무를 모두 오르게 되는 날이 아니라면, 항상 하루를 진행할 때에 A만큼 오르고, B만큼 내려와 총 A - B만큼 이동하게 됩니다.
또한 달팽이가 마지막 날에 나무를 오르게 된다면, 항상 낮에만 오르게 되므로, 마지막 날은 무조건 A만큼 나무를 오르게 된다는 것을 알 수 있습니다.
결국 우리는 이 문제를 ‘마지막 날에 A만큼, 나머지 날에는 A - B만큼 오르는 달팽이’ 문제로 생각할 수 있게 되므로, 마지막 날에 오르는 A를 제외한다면 우리는 V - A 높이의 나무를 매일 A - B씩 며칠만에 오를 수 있는지를 구하면 문제를 해결할 수 있습니다.
만약 이 A - B만큼 오르는 것을 하루하루 시뮬레이션을 한다면, 앞서 관찰에서 해결했던 방법에서 낮과 밤을 하루씩 건너뛰는 것만 달라지므로, 시간복잡도는 전혀 달라지지 않습니다. 이를 해결하기 위해 우리는 모든 날들을 시뮬레이션 하는 것이 아닌, 꼭 필요한 날들만 생각해줄 필요가 있습니다.
항상 달팽이는 하루만큼 지나면 나무에 조금이라도 더 올라가게 되므로, 만약 k일이 지나 달팽이가 처음으로 V - A만큼을 올라갈 수 있었다면, 우리는 다음 정보들을 얻을 수 있습니다.
- 0 ~ k - 1일이 지나는 것으로는 달팽이가 V - A만큼 올라갈 수 없다.
- k + 1일 이상이 지나는 것으로는 항상 V - A 이상 올라갈 수 있다.
이 정보를 이용하면 우리는 ‘V - A를 올라가는 가장 빠른 일수’ 를 구하는 문제로 볼 수 있게 되며, t일이 지나면 달팽이는 t * (A - B)만큼 올라간다는 사실을 이용해, 이분탐색으로 구한 날짜가 조건에 만족하는 날짜인지 확인할 수 있게 됩니다.
하루에 적어도 1만큼은 올라가기 때문에, 아무리 늦어도 V - A일 이후에는 올라간다는 사실을 이용하여 이분탐색의 범위를 정해줄 수 있고, 총 O(lg(V - A))에 문제를 해결할 수 있게 됩니다.
이 정도의 시간복잡도 만으로도 충분히 빠르게 해결할 수 있지만, 사실 위 방법보다 더 간단하게 문제를 해결할 수도 있습니다.
만약 V - A가 A - B의 배수가 된다면, 언제나 (V - A) / (A - B) 일이 지나면 V - A를 모두 오를 수 있게 되며, 만약 A - B의 배수가 아니라면 항상 하루만큼 더 지나게 된다면 V - A를 모두 오를 수 있게 됩니다. 이는 계산하는 것으로 어렵지 않게 알 수 있으며, 이를 이용해 이분탐색을 사용하지 않고도 며칠이 걸리는지 한 번에 계산할 수 있게 됩니다.
다만 V - A가 음수가 되는 경우도 있지만 실제 시간은 음수만큼 흐를 수 없기 때문에, 아무리 작아도 0일만큼 지나는 것으로 고려해준다면, 문제를 쉽게 해결할 수 있어 O(1)에 해결할 수 있게 됩니다.
최고의 피자 - JOI 2012 예선 3번
관찰
만약에 도우가 없다면 어떻게 될까요?
우리가 토핑 중에서 여러개를 골라서 1원당 가장 큰 열량을 가진 피자를 주문하는 상황으로 문제가 바뀌게 됩니다. 그렇다면 어떤 토핑들을 고르는게 가장 최대가 될까요?
정답을 바로 가장 큰 토핑을 하나만 사용하는 것입니다. 모든 토핑들은 다 같은 값을 가지고 있기 때문에, 우리가 구하고자 하는 1원당 열량은 (토핑 열량의 합) / (토핑의 수 * 토핑 가격) 이 됩니다. 이 때, 토핑 가격의 경우 항상 동일하게 되므로, 우리는 (토핑 열량의 합) / (토핑의 수) 를 최대화하는 것과 같이 볼 수 있는데, 이 상황에서는 가장 큰 하나의 토핑을 제외하고는, 다른 토핑들을 사용하지 않는 것이 가장 최선임을 어렵지 않게 알 수 있습니다.
그렇다면 지금 문제에서도 가장 큰 토핑 하나를 사용하는 것이 답이 될 수 있을까요?
앞선 예시를 살펴보는 것으로 확인해볼 수 있습니다.
만약 300인 2번 토핑만 사용한다면, 1원당 열량은 (200 + 300) / (12 + 2) = 20.83이 되어, 37.5보다 더 작아진다는 것을 알 수 있습니다. 이 이유는 우리가 기본으로 사용하는 도우의 열량과 그 때의 가격이 존재하여 토핑이 차지하는 가격 지분과 열량 지분이 달라지기 때문에, 토핑을 추가함으로 더 많은 이득을 볼 수도 있기 때문입니다.
풀이
그렇다면, 우리는 하나의 도우를 사용하는 시점에서 어떤 토핑을 사용해야 최고의 피자를 만들 수 있을까요?
앞선 방법과 같이 1개의 토핑만 사용하는 것은 꼭 답이된다는 보장이 없음을 알 수 있습니다.
즉, 우리는 0~N 종류의 토핑을 모두 사용해보는 것을 통해, 이중에 가장 큰 값이 되는 피자를 최고의 피자라고 생각할 수 있습니다.
허나, 이를 단순하게 구현한다면, 모든 토핑에 대해 사용한다, 하지 않는다 2개의 선택지가 있으므로, 총 2^N 가지의 경우가 존재함을 알 수 있습니다. 이를 어떻게 개선할 수 있을까요?
우리가 만약 K개의 토핑을 사용한다고 생각합니다. 이 때, 우리는 어떤 토핑을 사용하는 것이 최선이 될까요?
모든 토핑들은 모두 같은 가격을 가지고 있기 때문이, 총 추가되는 가격은 K * B임을 알 수 있습니다. 즉, 우리가 어떻게 선택해도 항상 같은 가격이 추가되므로, 우리는 최대의 열량을 가지는 K개의 토핑을 추가하는 것이 최선임을 알 수 있습니다.
즉, 0~N개의 토핑을 올리는 각각의 상황마다, 가장 큰 열량을 가진 토핑부터 피자에 추가하는 것이 항상 최선의 결과를 낼 수 있게 됩니다.
따라서, 모든 토핑들을 열량에 대한 내림차순으로 정렬한 이후, 0개의 토핑을 올리는 경우에서부터 가장 큰 토핑을 올린 1개의 토핑을 올리는 경우, 2~N번째 토핑까지 순서대로 피자에 올려보면서, 이중 가장 큰 1원당 열량을 가지는 값이 최고의 피자가 되는 것으로 계산하여 문제를 해결할 수 있습니다.
토핑을 정렬하는데 O(NlgN), 0~N번째 토핑을 순서대로 보는데 O(N)이 걸리므로, 우리는 총 O(NlgN)에 문제를 해결할 수 있습니다.
코드
Musical Notes 1
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[50010];
int main(){
int i, a, sum = 0;
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++){
scanf("%d", &a);
sum += a;
arr[i] = sum;
}
for(i = 0; i < m; i++){
scanf("%d", &a);
printf("%d\n", upper_bound(arr, arr + n, a) - arr + 1);
}
return 0;
}
Musical Notes 2
#include <bits/stdc++.h>
using namespace std;
struct Data{ int x, idx, v; };
int n, m;
int arr[50010];
Data marr[50010];
bool compare1(Data d1, Data d2){
return d1.x < d2.x;
}
bool compare2(Data d1, Data d2){
return d1.idx < d2.idx;
}
int main(){
int i, a, sum = 0;
scanf("%d %d", &n, &m);
for(i = 0; i < n; i++){
scanf("%d", &a);
sum += a;
arr[i] = sum;
}
for(i = 0; i < m; i++){
scanf("%d", &a);
marr[i] = (Data){a, i, -1};
}
sort(marr, marr + m, compare1);
a = 0;
for(i = 0; i < m; i++){
while(a < n && arr[a] <= marr[i].x) a++;
marr[i].v = a + 1;
}
sort(marr, marr + m, compare2);
for(i = 0; i < m; i++) printf("%d\n", marr[i].v);
return 0;
}
곱셈
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll c;
ll f(ll a, ll b){
ll now;
if(b == 1) return a % c;
now = f(a, b / 2);
return now * now % c * ((b % 2 == 1) ? a : 1) % c;
}
int main(){
ll a, b;
scanf("%lld %lld %lld", &a, &b, &c);
printf("%lld", f(a, b));
return 0;
}
달팽이는 올라가고 싶다
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a, b, v;
int main(){
ll now = 1;
scanf("%lld %lld %lld", &a, &b, &v);
v -= a;
printf("%lld", now + max(0ll, (v / (a - b) + ((v % (a - b) && v > 0) ? 1 : 0))));
return 0;
}
최고의 피자
#include <bits/stdc++.h>
using namespace std;
int n, a, b, c, max1, sum;
int arr[110];
int main(){
int i;
scanf("%d %d %d %d", &n, &a, &b, &c);
for(i = 0; i < n; i++) scanf("%d", &arr[i]);
sort(arr, arr + n);
max1 = c / a;
for(i = n - 1; i >= 0; i--){
sum += arr[i];
max1 = max(max1, (c + sum) / (a + (n - i) * b));
}
printf("%d", max1);
return 0;
}