BOJ 31963번: 두 배, 10885번: 수열의 장인 문제로 알아보는 "그리디 알고리즘에 수학 섞은 유형"

티스토리에는 굉장히 오랜만에 글을 적습니다. 오늘은 BOJ에 수록된 '두 배'와 '수열의 장인'이라는 두 문제를 살펴보며 그리디 알고리즘에 수학을 살짝 얹은 유형을 공략해 보겠습니다.

문제: 두 배

https://www.acmicpc.net/problem/31963

KOI 2024 1차대회 초등부, 중등부 기출문제인 '두 배'는 주어진 수열 A를 오름차순으로 만들기 위해 '특정 원소의 값을 2배로 하는 연산'을 여러 번 적용할 수 있을 때 최소 적용 횟수를 구하는 문제입니다.

시뮬레이션이 가능할까?

처음에 많이들 해 보는 생각이겠지만, [100, 99, 197, 393, ...]과 같은 수열을 생각해보면 시뮬레이션을 진행했을 때 수가 기하급수적으로 빠르게 커질 수 있음을 파악할 수 있습니다.

실제로 위 수열을 2배 연산을 적용해 오름차순으로 만든 결과는 [100, 198, 394, 786, ...]과 같이 됩니다. 결국 \(A_i=2^i\)로 근사되어 정수형의 표현 범위를 넘게 되죠.

인접한 두 수 사이의 관계를 오름차순으로 만드는 방법

수를 인접한 두 개만 생각해 본다면 연산 적용 횟수를 파악하는 것은 꽤 간단합니다.

제가 생각한 가장 편리한 방법은 \(\log 2\)를 사용하는 것입니다. 로그를 사용하면 인접한 두 수를 비교하면서 앞의 수가 더 큰 경우, 뒤의 수에 2를 몇 번 곱해야 하는지 빠르게 계산할 수 있습니다.

\(\log_2(A_{i-1} / A_i)\)를 계산하면 됩니다.

시뮬레이션하지 않고 어떻게 하지?

앞에서부터 순차적으로 '그리디하게' 오름차순으로 만드는 것이 최적임은 쉽게 파악할 수 있습니다. 그러니까 \(A_0\)은 연산 적용할 필요가 없지만, \(A_1\)부터는 연산 적용이 될 수 있습니다. 그런데 우리는 배열의 값들을 시뮬레이션하고 있지 않으므로 \(A_{i-1}\)에 두 배 연산을 n번 적용한 것을 '기억해 두어야' \(A_i\)에 두 배 연산을 몇 번 적용할지를 정확하게 계산할 수 있겠죠.

다행히도 \(\log_2(A_{i-1} / A_i)\) 계산 결과에 n을 단순히 더하면 \(A_i\)에 적용되는 연산 횟수를 얻을 수 있습니다. 그러므로 한 개의 추가 변수만 관리하면 됩니다. 그리고 \(A_{i-1}\)에 두 배 연산을 n번 적용했더라도 여전히 \(A_i\)보다 작아서 \(A_i\)에 연산을 적용할 필요가 없는 경우도 어렵지 않게 처리할 수 있습니다.

 

이렇게 '두 배' 문제를 풀 수 있습니다. 정답 코드는 다음과 같습니다.

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

from math import log2, ceil

ans, cur = 0, 0
for i in range(1, N):
    if log2(A[i - 1] / A[i]) + cur > 0:
        cur += ceil(log2(A[i - 1] / A[i]))
        ans += cur
    else:
        cur = 0
print(ans)

 

이 문제의 현재 시점 난이도는 Gold IV이고, KOI에 출제되는 문제 중에서는 평이한 수준입니다.

그런데, 이와 비슷하게 수열의 2배 연산을 다루는 문제가 9년 전 UCPC에 출제된 적이 있습니다. 지금부터 살펴보겠습니다.

문제: 수열의 장인

https://www.acmicpc.net/problem/10885

UCPC 2015 기출문제인 '수열의 장인'은 각 원소가 -2, -1, 0, 1, 2 중 하나인 주어진 수열 a에서, '연속된 부분 원소들의 곱'의 최댓값을 계산하는 문제입니다.

음수가 답이 될 수 있을까?

몇 가지 예제를 관찰하다 보면, 수열의 길이 N이 2 이상이므로 답은 항상 0 이상임을 알 수 있습니다.

그 이유는 a에 양수가 하나라도 있으면 그 양수 이상이 정답이며, 음수 2개인 경우에는 그 둘의 곱이 양수가 되기 때문입니다.

그러면 답은 0 또는 2의 거듭제곱 (\(1=2^0\) 포함)이 될 수 있겠네요.

중요한 것은 2의 개수와 부호구나!

수열이 연속하지 않은 음수와 0들로만 구성되는 일부 경우를 제외하고는 답이 2의 거듭제곱이므로, '두 배' 문제에서의 그리디 아이디어를 확장하면 앞에서부터 순차적으로 수열의 원소들을 살펴보면서 '현재까지 나온 2의 개수'를 변수로 관리하는 것이 좋겠습니다.

또, 곱이 음수인 경우에는 답을 업데이트해서는 안 되지만, 음수가 한 번만 곱해졌을 때 언제든지 답이 될 수 있으므로 '곱이 양수가 될 때만 현재까지 나온 2의 개수를 답에 업데이트'하는 로직을 구현하면 됩니다.

수열 중간에 0이 나오면 거기서부터 모든 것을 초기화해야 하는 점에 주의합시다.

양방향으로 그리디 해법을 시도해야 정답을 얻는다.

이 점은 이 문제에서 매우 중요한 관찰로서, [2, -1, 2, 2]라는 수열을 예로 들면 앞서 설명한 방식대로는 2라는 답을 얻지만, 실제 답이 4인 것이 명백합니다. 왜 이런 문제가 발생하는지 생각해 보면, 역방향으로도 그리디 해법을 시도해야 한다는 결론을 얻습니다.

 

이렇게 '수열의 장인' 문제를 풀 수 있습니다. 정답 코드는 다음과 같습니다.

양방향 그리디 풀이 구현을 위해 정답 구하는 로직을 함수로 뺐습니다. cur의 초기값이 -1인 이유는, 0으로 하면 최종 정답이 무조건 1 이상으로 나오는데 실제로 답을 업데이트하는 부분에 도달하지 못하면 최종 정답이 0이어야 하기 때문입니다.

def solve(A):
    cur, twos = -1, 0
    is_plus = True
    for a in A:
        if a == 0:
            twos = 0
            is_plus = True
            continue
        if a < 0:
            is_plus = not is_plus
        if a % 2 == 0:
            twos += 1
        if is_plus:
            cur = max(cur, twos)
    return cur

for _ in range(int(input())):
    N = int(input())
    A = [int(i) for i in input().split()]
    ans = max(solve(A), solve(A[::-1]))
    print(pow(2, ans, 1000000007) if ans != -1 else 0)

 

이 문제의 현재 시점 난이도는 Platinum V입니다. UCPC 문제 중 중위권에 해당하죠.

수학, 그리디가 동시에 있으니, 비교적 무난하다고 여겨지는 Platinum V라는 난이도로 매겨져 있어도 체감상 어렵게 느껴집니다.

 

이렇게 #수학 #그리디 알고리즘 두 태그가 동시에 붙은 두 재미난 문제를 풀어 봤습니다.

다음에는 또 다른 그리디 알고리즘 문제들을 소개드리고 싶네요! 그럼 오늘은 이만 안녕~