[백준] 27377: 읽씹 멈춰! - JAVA

29 May 2023 in Algorithm on 수학

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

풀이

그리디문제였다.

n개를 채워야 하는데 1번 추가는 s초, 현재 개수 곱하기 2는 t초가 걸린다.

최소 시간을 구하는 문제이다.

n개부터 시작하여 -1, /2 하면서 0으로 만들면 된다.

n이 홀수일때는 -1 을 해야하고,

n이 짝수일때는 n / 2 * s 가 t보다 크다면 /2해주고, 아니라면 -1로 n을 채운다.

s와 t가 10의 9제곱, n이 10의 18제곱이기때문에 BigInteger를 사용해야 한다.

---

메모리: 325656KB

시간: 1380ms

언어: Java 11

코드

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        StringTokenizer st;
        for (int tc = 0; tc < T; tc++) {
            long n = Long.parseLong(br.readLine());

            st = new StringTokenizer(br.readLine());
            BigInteger s = new BigInteger(st.nextToken());
            BigInteger t = new BigInteger(st.nextToken());

            BigInteger ans = BigInteger.ZERO;
            while (n > 0) {
                if (n % 2 == 1) {
                    n -= 1;
                    ans = ans.add(s);
                } else {
                    BigInteger num = new BigInteger(String.valueOf(n));
                    if (num.multiply(s).divide(BigInteger.TWO).compareTo(t) > 0) {
                        ans = ans.add(t);
                    } else {
                        ans = ans.add(s.multiply(num.divide(BigInteger.TWO)));
                    }
                    n /= 2;
                }
            }

            sb.append(ans).append("\n");
        }

        System.out.println(sb);

    }

}