백준 5710 (전기 요금) - java

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

 

문제

최근에 전기 회사는 전기 요금을 또 올렸다. 새로운 전기 요금은 아래 표에 나와있다. (사용량은 항상 양의 정수)

사용량 (Watt-hour)요금 (원)

1 ~ 100	2
101 ~ 10000	3
10001 ~ 1000000	5
> 1000000	7

 

위의 표를 읽는 방법은 다음과 같다.

사용량의 첫 100Wh의 가격은 1Wh당 2원이다. 다음 9900Wh (101 ~ 10000)의 가격은 1Wh당 3원이다. 이런식으로 계속 계산한다.

예를 들어, 10123Wh를 사용했을 때, 내야하는 요금은 2×100 + 3×9900 + 5×123 = 30515원이다.

전기 회사는 전기 요금을 인상하지 않고 돈을 더 버는 이상한 방법을 만들었다. 그 방법은 바로 사용한 전기의 양을 알려주지 않고, 얼마를 내야 하는지 알려주는 것이다. 전기 회사는 요금과 관련된 정보를 나타내는 두 숫자 A와 B를 알려준다. A와 B는 전기 회사에서 그 사람이 사는 건물에서 임의로 고른 이웃의 정보와 합친 요금이다.

• A: 이웃의 사용량과 사용량을 합쳤을 때 내야하는 요금
• B: 이웃의 전기 요금과의 차이 (절댓값)

위의 두 숫자를 이용해서 자신이 얼마를 내야 하는지를 계산할 수 없을 때는, 계산 요금을 100원을 더 내면 전기 회사에서 사용량을 알려준다.

상근이는 매우 전기를 아끼는 사람이다. 따라서, 항상 자신이 사는 건물에서 가장 전기를 적게 쓴다고 확신한다. 상근이는 돈도 전기만큼 아낀다. 따라서, 절대로 계산 요금을 지불하지 않고 자신이 직접 계산할 것이다.

예를 들어, A = 1100, B = 300이라고 하자. 이 정보를 이용하면, 상근이의 사용량은 150Wh, 이웃의 사용량은 250Wh임을 알 수 있다. 두 사람의 총 사용량은 400Wh이다. 따라서, A = 2×100 + 3×300 = 1100이 된다. 따라서, 상근이는 350원을 내면 된다. 상근이의 이웃은 2×100 + 3×150 = 650원을 내야 하고, B = |350 - 650| = 300이 된다.

A와 B가 주어졌을 때, 상근이가 내야하는 전기 요금을 구하는 프로그램을 작성하시오.

 

유형 : 이진 탐색

 

접근 방식

• 우선 A가 의미하는 것은 상근이와 이웃의 총 사용량을 합쳤을 때의 전기 요금이다.
• 해당 값을 표에 대해 역으로 계산하면 (상근이와 이웃의 전기 총 사용량)을 구할 수 있다.
• 문제에서 가장 큰 힌트가 주어졌다. 바로 '항상 자신이 사는 건물에서 가장 전기를 적게 쓴다고 확신'이라는 것이다.
  • 이 문장이 의미하는 것은 상근이의 전기 사용량은 절대 (총 사용량 / 2)를 넘지 않는다는 것이다.
  • 즉 이진 탐색 시 l = 0, r = total / 2 이라는 것이다.
• 또한 이진 탐색 시 상근이와 이웃의 사용량의 차이가 구해질 것이다.
  • 이 값이 B보다 작다는 것은 상근이의 사용량이 너무 많다는 것이다.
  • 반대로 B보다 크다는 것은 상근이의 사용량이 너무 적다는 것이다.

 

전체 코드

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

public class Main {

    static int A,B;

    static long totalUse = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        while(true){
            st = new StringTokenizer(br.readLine()," ");

            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            if(A == 0 && B == 0)
                break;

            totalUse = calTotal();

            long tmp = bs(totalUse);

            sb.append(tmp+"\n");
        }


        System.out.print(sb.toString());
        br.close();
    }

    static long bs(long tmp) {
        long l = 0;
        long r = tmp / 2;
        long mid = 0;

        while(l <= r) {
            mid = (l + r) / 2;

            long sang = cal(mid);
            long neighbor = cal(tmp - mid);

            if(Math.abs(sang - neighbor) == B){
                return sang;
            }

            if(Math.abs(sang - neighbor) > B) {
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }

        return 0;
    }
    static long cal(long use) {
        if(use >= 1 && use <= 100) {
            return 2 * use;
        }else if(use >= 101 && use <= 10000) {
            return 200 + 3 *(use - 100);
        }else if(use >= 10001 && use <= 1000000) {
            return 200 + (9900 * 3) + 5 *(use - 10000);
        }else if(use > 1000000) {
            return 200 + (9900 * 3) + (5 * 990000) + (7 * (use - 1000000));
        }

        return 0;
    }

    static long calTotal() {
        long tmpA = A;
        long result = 0;

        if(tmpA <= 200) {
            return tmpA / 2;
        }else{
            result += 100;
            tmpA -= 200;

            if(tmpA <= (9900 * 3)) {
                result += tmpA / 3;
                return result;
            }else {
                result += 9900;
                tmpA -= (9900 * 3);

                if(tmpA <= (990000 * 5)) {
                    result += tmpA / 5;
                    return result;
                }else {
                    result += 990000;
                    tmpA -= (990000 * 5);

                    result += tmpA / 7;
                    return result;
                }
            }
        }
    }
}