[백준] 17374번 비트베리 (자바 풀이)

문제

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

17374번: 비트베리

 

풀이

수학적으로 까다로운 문제였다.

 

이 문제는 두 가지 방법을 사용해서 해결할 수 있다. 

첫 번째 방법은 모든 비트와 베리를 코인으로 바꾼 뒤 코인을 비트와 1:1에 가깝게 배분하는 방법이다.

즉, 비트 -> 코인, 베리->코인 이후 코인-> 비트:코인 (1:1에 가깝게)

 

두 번째 방법은 모든 베리를 코인으로 바꾼 뒤 모든 코인을 비트로 바꾼 뒤 비트를 코인과 1:1에 가깝게 배분하는 방법이다.

즉, 베리->코인, 코인-> 비트 이후 비트-> 비트:코인 (1:1에 가깝게)

 

나는 두 가지 방법 중 두 번째 방법을 이용해서 해결했다.

 

모든 베리를 코인으로 바꾸고, 바꿀 수 있는 모든 코인을 비트로 바꾼 다음, 비트와 코인을 1:1 비율에 가깝게 배분해서 더 작은 값이 정답이다. 1:1에 가깝게 배분하는 것은 일차방정식의 해를 구하는 방식으로 구할 수 있다.

즉, y = coin + Bx 와 y= P - Ax의 교점을 구해서 이용하면 된다. 

이때 x가 정수가 아닐 수도 있으므로 x와 x+1 값을 모두 체크해줘야 한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Baekjoon_17374 {
    static int T,P,Q,A,B,C,D, coin, bitcoin;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            P = Integer.parseInt(st.nextToken());
            Q = Integer.parseInt(st.nextToken());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());
            D = Integer.parseInt(st.nextToken());
            
            coin = (Q/C)*D;        // 베리 -> 코인
            P += (coin/B)*A;    // 코인 -> 비트
            coin = coin % B;    // 비트로 바꾸고 남은 코인
            
            int x = (P-coin)/(A+B);    // (coin+Bx)=(P-Ax) 교점 구하기
            
            /*[x]+1 값도 포함해서 확인  */
            int ans = Math.max(Math.min(coin+(B*x), P-(A*x)),
                    Math.min(coin+(B*(x+1)), P-(A*(x+1))));
            
            System.out.println(ans);    
        }
    }
}