백준 17374번 - 비트베리

백준 17374번 - 비트베리

www.acmicpc.net/problem/17374

17374번: 비트베리

 

정말 정말 짜증 나는 문제였다.

 

문제를 처음 봤을 때 두 가지 방법이 떠올랐다.

 

1. 비트와 코인을 둘 중 하나로 몰고 브루트포스로 max값 구하기

 

2. 일차방정식 두 개의 교점 구하기

 

사실 방정식 문제를 많이 안 풀어봤고 해결법에 확신이 들지 않아서 가장 안전한 브루트포스로 먼저 도전했다.

 

당연히 맞을 줄 알았는데 틀렸습니다...

시간 초과도 아니고 틀렸습니다.. 이게 뭐지?? 하고 한 시간 넘게 고민했다.

 

곰곰이 생각해보다 코드에 오류가 있음을 발견했다. 

처음에 코드를 a!=b일 때와 a==b일 때 두 가지로 나눠서 풀었는데 이유는

a==b라면 (비트의 개수 + 코인의 개수)/2 만 출력하면 될 것 같아서였다.

 

갑자기 떠오른 생각이 a==b==1일 때만 그런 것 아닌가?

그렇다... 괜히 조금 더 간단히 풀려다가 1시간을 날렸다..

 

저 부분 코드만 빼고 다시 제출하니 이번엔 시간 초과... (이제 좀 정상 궤도 구만)

생각해 보니 당연히 시간 초과였고 혹시 컷팅으로 가능할까 해서 가능한 부분들을 컷팅해봤는데 역시 시간 초과..

 

결국 일차방정식밖에 답이 없음을 깨닫고 다시 풀었다..

 

식은 간단하다.

 

y = coin + bx와 y = q - ax의 교점을 구해주면 된다.

 

이때 주의할 점은

 

1. 교점의 x좌표가 정수가 아닐 수 있다! -> [x]+1, [x]-1에 대한 y값을 구해서 둘 중 max값이 답!

 

2. 비트나 코인을 한쪽으로 몰아야 한다! -> 그렇지 않으면 모든 경우를 탐색하지 않는다!

( 쉽게 말하면 정확한 x값을 구할 수가 없다..)

 

이렇게 하면 코드는 정말 간단하다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int t, p, q, a, b, c, d;
    cin >> t;
    while (t--) {
        cin >> p >> q >> a >> b >> c >> d;
        int coin = (q / c) * d;         // coin의 개수 구하기 (베리를 바꾸면 됨)
        p += (coin / b) * a;            // p를 최대화 시키기 (coin을 최소화 시키기)
        coin = coin % b;
        int x = (p - coin)/(a + b);        // 교점 구하기 (간단한 일차방정식의 교점 구하기) 
        // 아래는 구한 x좌표의 -1, +1한 값을 y에 대입한 값들 중 최댓값 구하기
        int ans = max(min(coin + (b * x), p - (a * x)), min(coin + (b * (x + 1)), p - (a * (x + 1))));
        cout << ans << "\n";
    }
}