[C++] 쿨한 물건 구매 (백준 1214번)

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

대충 이런식으로 써가면서 답을 어떤식으로 구해야 할지 생각해봤다. 
 
일단 p <= q 라고 가정하자.
d에서 q의 배수(tq)를 뺀 값(dif)을 p로 나누어서 나머지(rem)를 구했다. 이 때 나머지가 음수거나 0이면 p를 더해서 0보다 큰 값으로 바꾸어준다. 이 값이 가장 큰 경우에 지불할 수 있는 금액의 최소가 된다. 
그래서 아까 구한 나머지(rem)가 가장 클 때 답을 구하면 되는데, d에서 뺐던 그 q의 배수(tq)에 몫(quo)을 더해주면 된다. 몫(quo)은 아까 나머지에 p를 더하는 과정을 거쳤으면 그냥 몫으로 계산하면 되고, 그렇지 않았다면 몫+1로 계산하면 된다. 
아 그리고 아까 구한 나머지(rem)가 0일 때는 거스름돈 없이 딱 맞게 돈을 지불할 수 있는 경우이므로 바로 종료해도 된다.
 
그래서 모든 q의 배수에 대해서 반복을 돌리는데, 이 때 그냥 다 돌리면 시간초과가 나온다. 이미 나왔던 나머지 값이 나오면 반복된다는 뜻이므로 그 이후 계산은 할 필요가 없어져서 break 해주면 된다.
 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int d, p, q;
    cin >> d >> p >> q;

    if (p > q) {
        int tmp = p;
        p = q;
        q = tmp;
    }

    // p <= q

    int maxrem = 0;
    int maxa = 0;
    int tq = 0;

    int dif, rem, quo;
    while (1) {
        dif = d - tq;
        if (dif + p <= 0) break;
        rem = dif % p;

        if (rem == 0) {
            quo = dif / p;
            maxa = tq + p * quo;
            cout << maxa << '\n';
            return 0;
        } else if (rem < 0) {
            quo = dif / p;
            rem += p;
        } else {
            quo = dif / p + 1;
        }

        if (rem > maxrem) {
            maxrem = rem;
            maxa = tq + p * quo;
        } else if (rem == maxrem) {
            break;
        }

        tq += q;
    }
    
    cout << maxa << '\n';
}

(AC)
 

---

 
너무나 야매로 풀었다... 찝찝스
아마 D ≦ nP + mQ 를 전개해서 어쩌구 하는 풀이가 정해인 듯 한데 이해가 잘 안 돼서 좀 더 찾아보고 생각해봐야 할 것 같다.
 
[참고]
https://www.acmicpc.net/board/view/96265
https://kthng.tistory.com/74