본문 바로가기
BOJ

[Python] 백준 17374: 비트베리

by 야호호코코 2024. 7. 2.
반응형

 solved.ac 기준 Silver 1

 알고리즘을 푸는 데 수학적 지식이 무조건 있어야 하는 이유이다. 가끔씩 이렇게 수식으로 끝내야만 하는 문제가 나오므로 점화식을 살펴보는 능력을 준비하고 있어야 한다.

문제

비트베리는 국내 최다 사용자를 확보하고 있는 간편암호화폐 지갑이다. 비트베리의 가장 큰 특징 중 하나는 카카오 계정으로 지갑을 만들고, 전화번호로 암호화폐를 주고받을 수 있는 점이다.

 

페카즈는 비트베리의 특징을 이용해 자신이 보유한 다양한 종류의 암호화폐를 친구 빈센트와 상호 교환하고자 한다. 현재 페카즈의 비트베리 지갑 속에는 P개의 비트와 Q개의 베리가 들어 있다. 페카즈의 친구 빈센트는 엄청난 부자여서, 자신의 비트베리 지갑 속에 비트, 베리, 그리고 또 다른 단위인 코인과 비트코인을 각각 10100개씩 가지고 있다.

페카즈는 빈센트와 아래의 거래를 원하는 순서대로 원하는 만큼 반복할 수 있다.

  • 빈센트에게 비트 A개를 주고 코인을 B개 받는다.
  • 빈센트에게 코인 B개를 주고 비트를 A개 받는다.
  • 빈센트에게 베리 C개를 주고 코인을 D개 받는다.
  • 빈센트에게 코인 D개를 주고 베리를 C개 받는다.
  • 빈센트에게 비트 1개와 코인 1개를 주고 비트코인을 1개 받는다.

물론 거래를 하기 위해 빈센트에게 줘야 하는 암호화폐가 부족하다면 거래를 진행할 수 없다.

페카즈는 최선의 거래를 하여 자신이 갖고 있는 비트코인의 개수를 최대화하고자 한다. 페카즈가 만들 수 있는 비트코인의 최대 개수를 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 1,000)가 주어진다.

다음 T개의 줄에는 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 하나의 테스트 케이스를 구성하는 여섯 개의 정수 P, Q, A, B, C, D (0 ≤ P, Q ≤ 10,000, 1 ≤ A, B, C, D ≤ 10,000)가 공백 하나씩을 사이에 두고 주어진다.

출력

각각의 테스트 케이스마다, 페카즈가 만들 수 있는 비트코인의 최대 개수를 한 개의 줄에 출력한다.

예제 입력 1

3
2019 8 3 11 16 13
2019 7 27 2019 8 3
8 3 2019 7 29 2018

예제 출력 1

1584
1992
0

 

정답 코드

T = int(input())

for _ in range(T):

    P, Q, A, B, C, D = map(int, input().split())

    # 베리 -> 코인
    coin = D * (Q // C)

    # 코인 최소화, 비트 최대화
    P += (coin // B) * A  
    coin %= B

    cross = (P - coin) // (A + B)   # 교점

    bitcoin = max(min(coin + (B * cross), P - (A * cross)), 
                  min(coin + (B * (cross + 1)), P - (A * (cross + 1))))

    print(bitcoin)

 

 비트 코인의 최대값을 구하는 과정은 일차방정식의 교점을 구하는 것에서 착안했다. 일단 베리를 전부 코인으로 바꿔 준뒤, 코인을 최소화하고 비트를 최대화하여 첫 준비를 한다. 그리고 코인과 비트를 교환하면서 교점이 생기는 부분을 찾는ㄴ다. 하지만, 교점이 정수가 아닐수도 있으므로 -1, 1 지점도 탐색하면, 해당 교점이 비트코인의 최대 값이다.

 

참조

https://kimtaehyun98.tistory.com/30

반응형

'BOJ' 카테고리의 다른 글

[Python] 백준 1182: 부분수열의 합  (1) 2024.07.05
[Python] 백준 1189: 컴백홈  (1) 2024.07.01
[Python] 백준 15645: 내려가기 2  (0) 2024.06.30