[백준] 읽씹 멈춰! - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: 그리디

입력

출력

제한

풀이

구하고자 하는 것은 윤헌이가 하고 싶은 말을 정확히 n번 적는 데 걸리는 최소 시간이다.

최소 시간이 되게 하려면 어떻게 해야 할까?

최소 시간을 구하는 아이디어를 찾기 전에 조건을 확인해야 한다.

조건을 보면 n은 최대 10^18로 100경이다.

s와 t를 쓸지 비교할 구간은 2배가 되는 구간이다. 그러면 대략 60번 미만으로 비교를 해서 답을 구할 수 있다. (10^18 < 2^60 이기 때문에)

그러면 간단하다. 각 단계마다 비교를 해서 최소 시간이 될 수 있는 방법을 선택하면 된다.

예를 들어 입력값이 다음과 같을 때

1
17
1 5

첫 번째 단계 17/2 = 8..1이다.

정확히 n번을 입력해야 되기 때문에 1은 무조건 타이핑을 해야 한다.

그러면 8에서 16을 만들어야 하는데 이때 2배를 하는 t와 타이핑을 통한 (16 - 8) * s를 비교한다. 그러면 t가 더 작기 때문에 t를 answer에 더해주면 된다.

이를 1이 될 때까지 반복하고

1일 때는 무조건 타이핑을 해야 하기 때문에 s를 더해주면

결괏값이 14가 나오게 된다.

주의할 점은 Java에서 BigInteger를 사용해야 정확한 값을 출력할 수 있다.

소스코드

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

public class Main {
    static int tc;
    static StringBuilder sb = new StringBuilder();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        for(int i=0; i<tc; i++) {
            long n = Long.parseLong(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            
            sb.append(answer(BigInteger.valueOf(n), BigInteger.valueOf(s), BigInteger.valueOf(t))).append("\n");
        }
        System.out.println(sb.toString().trim());
    }
    
    static BigInteger answer(BigInteger val, BigInteger s, BigInteger t) {
        BigInteger result = new BigInteger("0"); //처음에는 할 말을 무조건 타이핑 해야됨
        result = result.add(s);
        while(!val.equals(BigInteger.valueOf(1))) {
            BigInteger[] dVal = val.divideAndRemainder(BigInteger.valueOf(2));
            BigInteger difVal = val.subtract(dVal[0]);
            if(dVal[1].equals(BigInteger.valueOf(1))) {
                //val이 홀수인 경우에는 타이핑해줘야됨
                result = result.add(dVal[1].multiply(s));
                difVal = difVal.subtract(BigInteger.valueOf(1));
            }
            if(difVal.multiply(s).compareTo(t) == -1) {
                // difVal * s (타이핑 시간)이 t (복/붙 시간)보다 작다면
                result = result.add(difVal.multiply(s));
            } else {
                //복/붙 시간이 같거나 작다면
                result = result.add(t);
            }
            val = dVal[0];
        }
        return result;
    }
}