[C++] 10246번 부동산 경매

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

---

 

25/01/05

 

 

간단한 수식 정리 문제인데, 나이브하게 돌려서 미리 계산해놓고 푸는 풀이도 꽤 빠른 것 같다.

---

 

문제 접근 방식:

 

 

각 테스트 케이스 별로 다음을 계산하면 된다. 두 수 사이의 연속 된 수들의 합으로 $N$을 표현할 수 있는 경우의 수.

 

유의할 점은 테스트 케이스의 개수가 안나와있고, 시간 제한은 10초이며, 실제로도 테스트 케이스의 개수가 매우 많다는 점이다.

 

$N$의 범위가 $1 \ 000 \ 000$까지이기 때문에, 어떤 사람들은 미리 그 크기의 배열을 선언해두어 계산을 다 한 후에 쿼리를 처리하는 방식을 하기도 했다.(이 경우 쿼리 당 소요되는 시복도는 상수다.)

 

나의 경우는 수식으로 접근하여, 쿼리 당 $\mathcal{O}(\sqrt{N})$으로 구할 수 있게 끔 했다.

 

먼저, 두 수를 $p, q$라고 하고, 편의 상 $p > q$라고 가정했다.

 

그러면 $q+1$부터 $p$까지 모두 더한 합이 $N$이 되야하므로, 다음을 만족시켜야 한다.

 

$$\frac{p(p+1)}{2} - \frac{q(q+1)}{2} = N$$

 

양 변에 2를 곱하고 인수분해를 하면 다음과 같다.

 

$$(p-q)(p+q+1) = 2N$$

 

$p-q = A, p+q+1 = B$라고 해보자. 즉, $2N$은 두 정수의 곱으로 쪼개진다. 또한 이 정수 $A, B$는 $A < B$ 조건을 만족시킨다.

 

따라서, 일반적인 약수 구하는 알고리즘처럼 최대 $\sqrt{2N}$까지만 돌아도 충분하다.

 

$2N$이 어떤 수($A$)로 나누어 떨어진다면, 이를 통해 $A, B$를 설정하고, 이를 통해 $p$와 $q$를 구할 수 있다.

 

$p = (B+A-1) / 2, q = (B-A-1) / 2$이다. 여기서 한 가지 빼먹을 수 있는 사실은, $A$와 $B$ 둘은 항상 홀짝이 다르다는 사실이다.(그렇지 않다면 성립이 되지 않는다.)

 

이를 통해 구한 $p, q$는 우리가 이전에 설정했던 조건 $p > q$조건을 만족시켜야 한다. 또한, $q > 0$이어야 한다.(0번 집은 존재하지 않기 때문에)

 

이 조건을 모두 만족시킨다면 경우의 수를 +1시켜주면 된다.

 

구하면서 실수하기 쉬운 부분들은, 1. $A$와 $B$가 홀짝이 다르다는 점, 2. $p > q > 0$이라는 점, 3. $\sqrt{2N}$만 돌아도 충분하다는 점이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 10246번 부동산 경매
// 수학
/*
접근 방법:

*/
#include <iostream>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

void solve(int N){
    int A, B, p, q, ans = 0;
    for (int i = 1; i*i <= 2*N; i++){
        if ((2*N) % i == 0){
            A = i; B = (2*N)/i;
            if ((A%2)^(B%2) == 0) continue;
            p = (B+A-1)/2; q = (B-A-1)/2;
            if (p > q && q > 0) ans++;
        }
    }
    cout << ans << endl;
    return;
}

int main(void){
    fastio;
    int N;
    while (true){
        cin >> N;
        if (N == 0) return 0;
        if (N == 1) cout << 0 << endl;
        else solve(N);
    }
}