PS와 개발을 공부하자

Topcoder SRM 522 Div1(Medium) CorrectMultiplication 본문

Algorithm/Problem Solving

Topcoder SRM 522 Div1(Medium) CorrectMultiplication

sgc109 2017.05.20 09:48
문제 링크


\(1\leq{a,b,c}\leq{10^9}\) 일 때, 
A * B = C 를 만족하면서 |A-a| + |B-b| + |C-c| 가 최소가 되게 하는 자연수 A,B,C 에 대하여
|A-a| + |B-b| + |C-c| 를 구하는 문제이다.

처음에 삼분탐색 등으로 구하려 했는데 풀리지 않았다. 애초에 삼분탐색만으로는 풀 수 없는 문제같다.
우선 가장 중요한 것 중 한가지는 A가 정해지면 |A-a| + |B-b| + |C-c| 가 최소값이 되기 위한 B와 C는
자동으로 결정 된다는 것이다. 그 이유는
우선 우리는 A가 이미 정해졌기 때문에 |A-a| + |B-b| + |C-c|를 최소로 만들기 위해서는 최대한
B를 b와 같게 만들고 C를 c와 같게 만들어야 한다. 그런데 C는 A와 B의 곱으로 이루어 지기 때문에
B를 b에 우선으로 맞췄다가는 C가 c와 많이 달라질 수가 있기 때문에 그리디 하게 C를 c에 맞추는게 우선이라는 것을
알 수가 있다. 그러면 A가 정해졌으면 C는 c와 최대한 같아야하므로 즉 A*B가 c와 최대한 같아야 하는것이므로
B는 c/A (상수) 이어야한다. 하지만 A,B,C는 자연수 이기 때문에
c가 A로 나누어 떨어지지 않을 수가 있고 그렇기 때문에 오차가 발생할 수가 있다. 하지만 그렇다고 해도 소수점
오차이기 때문에 c/A, c/A-1, c/A+1 이렇게 세가지를 모두 봐준다면 될 것이다. 아무튼 그럼 A와 B가 정해졌으니
C는 당연히 A*B이기 떄문에 정해진다. 즉, A가 정해지면 |A-a| + |B-b| + |C-c| 가 최소가 되기 위한 A,B,C 는 모두
정해진다는 것을 알 수가 있다. 그러면 A가 될 수 있는 후보를 몇개를 봐줘야 할 것인가가 중요하다.
일단 a = 10억, b = 1, c = 10억 이라면 답은 A가 10억일 때이다. 그렇기 때문에 대충 A의 후보가 1~10억 정도는
될 것이라고 생각할 수가 있다. 하지만 다르게 한번 생각해 보자. A의 후보를 고르는게 아니라 C의 후보가
몇가지나 되나 생각해보자. 그러면 A는 C를 나누는 수이기 때문에 C의 후보보다 A의 후보는 훨씬 적을 것이다.
우선 A=B=C=1 이라면 |A-a| + |B-b| + |C-c| 는  a+b+c-3 이기 떄문에 답의 limit은 아무리 커도 a+b+c-3 보다
작거나 같을 것이라는 것을 알 수가 있다. 그러면 |A-a| + |B-b| + |C-c|를 최소로 만들려면
C 는 아무리 커도 a+b+2c-3 보다 작거나 같을 것이다. 그 이상 커지면 limit 보다 |A-a| + |B-b| + |C-c| 가
커지기 때문에 답이라는 사실이 모순이기 때문이다. 그럼 1 <= C <= a+b+c-3 라는 사실을 알게 되었다.
그럼 A는 C를 나누는 수이기 때문에 C의 제곱근까지 돌리면서 답을 갱신해주면 된다.
그런데 이렇게 하면 A가 C의 제곱근 보다 작거나 같을 때만 계산하는 것이기 때문에 A와 B를 바꿔서도 한번
계산해줘야 한다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
class CorrectMultiplication {
public:
    long long getMinimum(int a, int b, int c) {
        ll limit = (ll)a + b + 2*- 3;
        ll ans = 1e18;
        for(ll A = 1 ; A * A <= limit; A++){
            for(int k = -1 ; k <= 1; k++){
                int B = c/A+k;
                if(!B) continue;
                ans = min(ans, abs(A-a)+abs(B-b)+abs(A*B-c));
                ans = min(ans, abs(B-a)+abs(A-b)+abs(A*B-c));
            }
        }
        return ans;
    }
};
 
cs


0 Comments
댓글쓰기 폼