[Algo] 백준 27377 읽씹 멈춰! JAVA

문제 바로가기 : https://www.acmicpc.net/problem/27377

메모리 : 320432KB

시간 : 1192ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int TC = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < TC; tc++) {
            BigInteger N = new BigInteger(br.readLine());
            st = new StringTokenizer(br.readLine());
            BigInteger s = new BigInteger(st.nextToken());
            BigInteger t = new BigInteger(st.nextToken());
            BigInteger ans = new BigInteger("0");
            while (!N.equals(BigInteger.valueOf(0))) {
                if (N.remainder(BigInteger.valueOf(2)).equals(BigInteger.valueOf(0))) {
                    N = N.divide(BigInteger.valueOf(2));
                    if (N.multiply(s).compareTo(t) == 1) {
                        ans = ans.add(t);
                    } else {
                        ans = ans.add(s.multiply(N));
                    }
                } else {
                    N = N.subtract(BigInteger.valueOf(1));
                    ans = ans.add(s);
                }
            }
            sb.append(ans).append("\n");
        }
        System.out.print(sb);
    }
}

 

보기쉬운 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static <T> void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		for(int tc=0; tc<TC; tc++){
			long N=Long.parseLong(br.readLine());
			st=new StringTokenizer(br.readLine());
			int s=Integer.parseInt(st.nextToken());
			int t=Integer.parseInt(st.nextToken());
			long ans=0;
			long cnt=N;
			while(cnt>0){
				if(cnt%2==0){
					cnt/=2;
					if(cnt*s>t){
						ans+=t;
					}else{
						ans+=s*cnt;
					}
				}else{
					cnt-=1;
					ans+=s;
				}
			}
			sb.append(ans).append("\n");
		}
		System.out.print(sb);
	}
}

 

풀이

long으로 풀었는데 계속 틀렸습니다 나와서ㅜ BigInteger써야하는 문제였다. BigInteger 코드가 보기 힘드니 보기쉬운 사칙연산코드를 사용한 것도 올린다.

0에서 N으로 가는 코드로 시도해보니 시간초과가 났다. 아무래도 바텀업은 경우의 수가 많은데, N에서 0으로 가는건 계산할 경우의 수가 정해져있어서 그런 것 같다.

그리디를 이용해 풀 수 있다.

1. N에서 0으로 가는데, 복붙이 가능할때(2로 나누어질때)는 복붙했다고 친다. 그 외에는 타자로 간주한다.
2. 복붙했을 때가 타자쳤을 때 보다 유리해야한다. (복붙으로 쓸 수 있는 개수/ 복붙했을때 소모값) > 하나씩 쳤을 때 값
3. 복붙보다 타자가 유리할 때, 그 유리한 값까지는 타자로 쳐야한다.