[백준] 10246 : 부동산 경매

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

10246번: 부동산 경매

---

• 완전탐색을 돌린다고 할지라도, 불필요한 탐색을 줄일 필요는 있다.
• 문제에서 연속된 집들의 합으로만 맞춰야 하기 때문에, n 개의 연속 값들에 대한 수식을 세워볼 수 있다.
• 2개의 연속된 값들은 n 과 n +1 이므로 2n+1 로 나타낼 수 있고, 3개의 연속값들은 똑같은 방식으로 3n+3 이 된다.
• 같은 방식으로 최대로 가능한 연속값의 개수인 1413 개 (1~1413 까지의 합 = 998991) 까지의 수식을 구할 수 있다.
• 각 수식마다 1 부터 1000000 까지 수식으로 표현 가능한 값들에 대해서 경우의 수를 1씩 추가해준다.

---

#include <iostream>
#include <vector>

using namespace std;

int cumsum, x;
vector<int> values(1000001, 1);                         // 모두 자기 자신만을 가질 수 있기 때문에 최소 1 의 값들은 가짐 (1원 제외)

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

    values[1] = 0;
    for(int cur = 2 ; cur <= 1413 ; cur++)              // 1부터 1413 까지의 연속합이 100만에 가장 가까움 - 1413 은 최대로 연속 가능한 값의 개수
    {
        cumsum += cur-1;
        for(int i = 2 ; cur*i+cumsum <= 1000000 ; i++)  // 2개가 연속된 값의 경우 2x+1, 3개는 3x+3, 4개는 4x+6 의 꼴로 표현 가능
        {
            values[cur*i+cumsum]++;                     // 따라서 해당 표현식으로 가능한 모든 값들에 대해서 경우의 수 하나씩 올려줌
        }
    }

    cin >> x;
    while(x)
    {
        cout << values[x] << '\n';
        cin >> x;
    }
}