BOJ1214: 쿨한 물건 구매

작성일

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

  • 솔직히 수론이 너무 어렵다.
  • 이번 문제의 핵심은 5원과 7원이 있을때, 35원마다 패턴이 반복되는 것을 알아차리는 것이다.
  • 그러면 77원을 만들어야 할 때 70 + 7로 연산이 확 줄어든다.
  • 그런데 주의해야할 점이 35 + 13 = 48 같은 경우다.
    • 이 경우는 덮어놓고 35를 다 빼버리면 13만 남아서 표현이 안된다.
    • 48 = 4*5 + 4*7로 표현이 가능하다.
    • 즉 5*7로 나눠서 남기면 안되고, 5*7*2로 나눠서 남겨야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL gcd(LL a, LL b){return a%b?gcd(b,a%b):b;}

int main() {
  LL X, Y, Q;
  cin >> Q >> X >> Y;
  if(Y > X) swap(X, Y);
  LL opp = 0;
  LL lcm = X * Y;
  if (Q % lcm == 0) {
    cout << Q;
    return 0;
  }
  LL rQ = (Q / lcm - 1) * lcm;
  if (rQ < 0) rQ = 0;
  Q = Q - rQ;

  LL cur = (Q / X) * X + (Q % X ? X : 0);
  LL ans = cur;

  while(cur >= 0) {
    /* printf("%lld + %lld = %lld, %lld\n", cur, opp, cur + opp, Q); */
    ans = min(ans, cur + opp);
    if (cur + opp == Q)
      break;
    cur -= X;
    int R = Q - cur;
    opp = (R / Y) * Y + (R % Y ? Y : 0);
  }
  cout << rQ + ans;
}