Baekjoon 31963. 두 배 / Java, Python

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

알고리즘 설명

문제 설명

문제는 주어진 수열에서 어떤 연속된 두 수 a[i-1]와 a[i]가 있을 때, a[i-1]가 a[i]보다 작지 않도록 하기 위한 최소한의 조작 횟수를 구하는 문제, 조작은 a[i]를 2의 제곱만큼 증가시키는 것입니다.

코드 설명

비율 계산: 현재 수 arr[i]와 이전 수 arr[i-1]의 비율을 계산. arr[i-1]가 arr[i]보다 크면 arr[i]를 적절히 증가시키는 것이 필요하다. 비율을 구하는 식은 Math.log(arr[i-1] / arr[i]) / Math.log(2). 이를 Math.ceil 함수를 사용해 올림

조작 횟수 누적: 각 단계에서 필요한 조작 횟수를 누적합니다. cnt_arr는 각 단계에서의 조작 횟수를 기록

시간복잡도 : O(N)

자바 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();  // 수열의 길이
        int[] arr = new int[n];  // 수열을 저장할 배열

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();  // 수열의 요소들 입력
        }
        System.out.println(sol(arr, n));  // 조작 횟수 계산 결과 출력
    }

    // 연속된 두 수를 비교하여 조작 횟수를 계산하는 함수
    public static long sol(int[] arr, int n) {
        long tmp = 0;  // 총 조작 횟수
        long[] cnt_arr = new long[n];  // 각 인덱스에서의 조작 횟수를 기록하는 배열
        for (int i = 1; i < n; i++) {
            // 이전 수를 현재 수로 나눈 비율을 기반으로 필요한 2의 제곱 횟수를 계산
            double ratio = Math.ceil(Math.log(arr[i - 1] / (double)arr[i]) / Math.log(2)) + cnt_arr[i - 1];
            if (ratio > 0) {
                cnt_arr[i] = Math.max(0, (long)ratio);  // 조작 횟수 계산
                tmp += cnt_arr[i];  // 총 조작 횟수에 추가
            }
        }
        return tmp;  // 최종 조작 횟수 반환
    }
}

파이썬 코드

import math
import sys; input = sys.stdin.readline

# 연속된 두 수를 비교하여 조작 횟수를 계산하는 함수
def sol(arr, n):
    tmp = 0  # 총 조작 횟수
    cnt_arr = [0] * n  # 각 인덱스에서의 조작 횟수를 기록하는 배열
    for i in range(1, n):
        # 이전 수를 현재 수로 나눈 비율을 기반으로 필요한 2의 제곱 횟수를 계산
        ratio = math.ceil(math.log2(arr[i - 1] / arr[i])) + cnt_arr[i - 1]
        if ratio > 0:
            cnt_arr[i] = max(0, ratio)  # 조작 횟수 계산
            tmp += cnt_arr[i]  # 총 조작 횟수에 추가
    return tmp  # 최종 조작 횟수 반환

n = int(input())  # 수열의 길이 입력
arr = list(map(int, input().split()))  # 수열의 요소들 입력
print(sol(arr, n))  # 조작 횟수 계산 결과 출력