[백준 31963] 두 배

이 문제는 2024 정보올림피아드 1차 대회 초등부 2번, 중등부 1번 문제 입니다. 문제는 아래 링크에서 확인 바랍니다.

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

 

수열을 오름차순으로 만드는 문제로 앞의 수보다 다음 수가 작다면 두 배씩 커지게 만들어 수열을 오름차순을 만들어 주면 됩니다. 첫 번째 예제를 확인해 보며 문제를 이해해 보겠습니다.

3, 1, 4, 1, 5

첫 번째 예제의 숫자입니다. 두 번째 숫자인 1은 3보다 작기 때문에 오름차순이 되지 않습니다. 따라서 여기에 2를 곱해줍니다. 2를 곱하면 2가 되어 아직 3보다 작습니다. 따라서 2를 더 곱해주어 4를 만들어 줍니다. 이제 오름차순이 되었기 때문에 다음 숫자를 확인합니다. 세 번째 숫자는 4로 오름차순이기 때문에 다음 숫자를 확인합니다. 네 번째 숫자는 1이기 때문에 오름차순이 되게 하기 위해 2번의 2를 곱해줍니다. 그럼 전체가 모두 오름차순이 되고 두 배 연산은 총 4번 진행한 것입니다. 따라서 정답은 4가 됩니다.

이렇게 간단하게 문제를 해결해 보겠습니다.

33점 풀이

위와 같은 방식으로 무작정 앞의 수와 비교하여 두 배씩 늘려주면 N이 10 이하인 경우를 해결할 수 있습니다.

입력 받기

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

길이 N을 입력 받습니다. 다음으로 수열 arr을 입력 받습니다.

문제 해결

cnt = 0
for i in range(1, N):
    while arr[i] < arr[i - 1]:
        arr[i] *= 2
        cnt += 1

print(cnt)

cnt는 두 배를 진행할 연산 횟수 입니다.

다음으로 수열의 숫자를 확인할 반복문을 만들어 줍니다. 앞의 수를 확인하여 만약 작다면 커질때 까지 2를 곱해줍니다. if 문이 아닌 while문을 사용한 것을 주의해야 합니다. 2를 곱하는 연산이 몇 번 진행될지 모르기 때문에 if문을 사용하면 한 번만 곱해줍니다. while문을 사용해여 앞의 수보다 커질때까지 두 배를 늘려줄 수 있습니다.

이렇게 제출하면 33점을 받을 수 있습니다.

100점 풀이

앞서 33점을 받으면서 시간복잡도를 해결할 수 있는 방법 중 하나가 while문을 제거하는 방법 입니다. 오름차순을 만들기 위해 무작정 2씩 곱해주어 비교해 주었는데 매 번 곱해주는 것보다는 한 번에 계산할 수 있다면 시간복잡도를 줄일 수 있습니다. 이것을 계산하려면 log를 알아야 하는데 초등학생 문제에서 log를 사용하는 것은 문제의 취지에 어긋난다고 생각되어 다른 방식을 생각해야 합니다. log 사용하는 방법은 아래에 추가로 작성해 놓기로 하고 지금은 다른 방식으로 풀어 보겠습니다.

1025, 1, 4, 3

위와 같은 숫자가 있습니다. 이것을 오름차순으로 정렬하기 위해 두 배씩 곱한다면 먼저 두 번째 숫자 1이 첫 번째 숫자 1025보다 크게 만들기 위해서 11번 두 배 연산으로 2048을 만들어야 합니다. 다음 세 번째 숫자는 4를 2048보다 크게 만들기 위해서 9번의 두 배 연산을 해야 합니다. 마지막으로 3은 10번의 두 배 연산을 해야 합니다.

이것을 33점 풀이처럼 하나하나 다 계산하는 것이 아니라 앞에서 이미 계산한 두 배 연산은 그냥 더해주는 것이 시간복잡도를 줄일 수 있습니다.

두 번째 숫자 1이 1025보다 크게 만들기 위해서 11번의 연산은 그냥 계산하지만 세 번째 숫자 4를 2048보다 크게 만들기 위해 모두 계산하는 것이 아니라 1과의 차이를 계산합니다. 1을 4로 만들기 위해서 두 배 연산을 두 번해야 합니다. 그럼 2048을 만들기 위해 11번의 연산에서 두 번을 뺀 9번을 더해주면 됩니다.

네 번째 숫자 3역시 2048로 두 배 연산을 계산하는 것이 아니라 원래 숫자인 4보다 크게 만들기 위해 몇 번 연산을 해야 하는지 계산하는 것입니다. 3이 4보다 크게 만들려면 한 번의 연산이 필요합니다. 여기에 앞의 연산 횟수인 9번을 더하면 됩니다.

코드 작성

그럼 위의 100점 코드를 직접 작성해 보겠습니다.

입력 받기

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

입력 받는 부분은 33점 풀이와 같습니다.

뒤의 숫자와 몇 배 차이인지 확인

cnt = [0] * N
for i in range(1, N - 1):
    temp = arr[i]
    while temp <= arr[i + 1]:
        temp <<= 1
        cnt[i] += 1
    if cnt[i]:
        cnt[i] -= 1

cnt는 앞의 숫자가 뒤의 숫자와 몇 배 차이인지 확인합니다. 위의 예제 두 번째 숫자, 세 번째 숫자를 보면 1이 4보다 두 배 차이가 두 번인 것을 확인하는 것입니다. 그래야 나중에 뒤의 숫자가 앞의 숫자보다 크다면 몇 번 두 배 연산을 덜해도 되는지 알 수 있습니다. 마지막 if문인 cnt[i]가 0보다 크다면 1을 빼줍니다. 오름차순으로 정렬을 원하기 때문에 한 번의 연산은 빼주어야 합니다. 1이 4보다 크게 만들기 위해서는 세 번의 연산으로 8을 만들어야 합니다. 이는 우리가 원하는 값이 아닙니다. 세 번에서 한 번을 뺀 두 번으로 해주어야 합니다.

	1025	1	4	3
필요한 연산	첫 번째 숫자	두 배 연산 2번 으로 4로 만듬	3보다 크기 때문에 넘어감	마지막 숫자
cnt값	0	2	0	0

앞의 숫자와 몇 배 차이인지 확인

rst = [0] * (N + 1)
for i in range(1, N):
    temp = arr[i]
    while temp < arr[i - 1]:
        temp <<= 1
        rst[i] += 1
    if cnt[i] < rst[i]:
        rst[i + 1] += rst[i] - cnt[i]

rst는 앞의 숫자와 몇 배 차이인지 계산하는 것입니다. 위의 예제의 세 번째 숫자 4와 네 번째 숫자 3의 경우 3을 두 배 연산 한 번 하면 4보다 크게 만들 수 있습니다. 이 값을 누적으로 계산해 주어 앞에서 이미 커진 숫자에 대해 더 계산을 하지 않아야 시간 복잡도를 줄일 수 있습니다.

rst 값이 cnt 값보다 더 크다는 것은 앞의 숫자보다 작아 두 배 연산을 rst 값만큼 더 해주었다는 뜻입니다. 여기에 그냥 cnt값을 더하면 이미 두 배연산을 한 곳에 또 두 배연산을 한것이 됩니다. 따라서 cnt 값을 빼주어야 우리가 원하는 값을 찾을 수 있습니다.

1025 1 4 3

	1025	1	4	3
필요한 연산	첫 번째 숫자	1025보다 크게 만들기 위해 11번의 2배 연산 필요	1보다 크기 때문에 연산 필요 없음	4보다 크게 만들기 위해 두 배 연산 한 번 필요
rst 값	0	11	9	10

합계 출력

rst 값을 모두 구했다면 이것을 다 더해주면 됩니다. 하지만 rst의 마지막 값을 더해주면 안됩니다. rst의 다음 값을 누적해서 만들기 위해 rst의 배열의 길이를 N + 1로 해주었습니다. 이것은 배열의 길이로 인한 오류가 발생하지 않기 위해서 입니다. 실제로는 마지막 값은 사용이 되지 않습니다.

print(sum(rst[:-1]))

전체 코드

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

cnt = [0] * N
for i in range(1, N - 1):
    temp = arr[i]
    while temp <= arr[i + 1]:
        temp <<= 1
        cnt[i] += 1
    if cnt[i]:
        cnt[i] -= 1

rst = [0] * (N + 1)
for i in range(1, N):
    temp = arr[i]
    while temp < arr[i - 1]:
        temp <<= 1
        rst[i] += 1
    if cnt[i] < rst[i]:
        rst[i + 1] += rst[i] - cnt[i]

print(sum(rst[:-1]))

log 사용 풀이

마지막으로 log를 사용한 풀이를 알아보겠습니다. 초등학교, 중학교 수준에서는 이해가 안될 수 있으니 log를 모른다면 그냥 넘어가도 됩니다.

이것은 세그먼트 트리를 구할 때 log를 사용해서 트리의 깊이를 구하는 것과 똑같습니다. 세크먼트 트리 역시 이진 트리이기 때문에 두 배 연산과 같은 형태 입니다. 세그먼트 트리에서 사용한 방법은 아래 링크를 확인 바랍니다.

https://wikidocs.net/209447

01. 구간 합 구하기[백준 2042]

 

log 를 사용해 어떤 값이 2의 몇 배인지 찾습니다. 그리고 ceil을 통해 그 값을 올림해 줍니다. 그럼 위와 같이 계산하지 않아도 쉽게 값을 찾을 수 있습니다.

전체 코드

from math import ceil, log2
N = int(input())
arr = list(map(int, input().split()))

rst = 0
cnt = [0] * N

for i in range(1, N):
    log_rst = log2(arr[i - 1] / arr[i])
    temp = ceil(log_rst) + cnt[i - 1]
    if 0 < temp:
        cnt[i] = temp
        rst += cnt[i]

print(rst)

log_rst값은 앞의 숫자와 뒤의 숫자가 몇 배 차이인지 계산한 것을 log로 변환 하는 것입니다. 위에서 봤던 예제에서 1025, 1의 경우 1025 / 1은 1025로 log2로 계산하면 10보다 약간 큰 수가 나올 것입니다. 1, 4의 경우는 -2가 나오게 됩니다. 마지막 4, 3의 경우는 0보다는 크고 1보다는 작은 수가 나오게 됩니다. 이 수들을 ceil 하면 올림이 되기 때문에 각각의 temp 값은 11, -2, 1이 됩니다. 여기에 앞에 있던 cnt 값을 빼면 11, 9, 10 이 됩니다. temp 값이 0보다 작게 된다는 것은 이미 오름차순 정렬이 되어 있다는 뜻이기 때문에 그냥 넘어갑니다. 그렇게 구한 최종 rst값이 우리가 구하려는 답이 되는 것입니다.

정리

두 배 라는 문제를 접근하는 방법인 33점 풀이부터 시간 복잡도를 줄일 수 있는 100점 풀이, 마지막으로 log를 사용한 풀이까지 알아보았습니다. log 풀이는 고등학교 이상이나 풀 수 있기 때문에 넘어가도 됩니다. 쉽지 않은 문제이기 때문에 실제 시험에서는 당황해서 문제를 못 풀 수 있습니다. 그런 경우는 빠르게 33점 풀이부터 만들어 33점을 확보하고 100점에 도전하는 것이 좋습니다.