백준18665 IQ Test

작성일 | In

문제 링크

  • http://icpc.me/18665

풀이

재귀를 적절히 돌려 정답을 구할 수 있습니다.

N을 만드는 함수 dfs(N)을 정의합시다.
N을 만들기 위해서는 $N = x^2 - y$를 만족하는 두 정수 x와 y가 존재해야 합니다. 그러므로 N을 적절히 분할해서 x, y를 찾은 다음 dfs(x)와 dfs(y)를 호출해주면 됩니다.

N을 “적절히” 분할하는 것이 문제인데, 저는 $x = \lceil \sqrt N \rceil, y = x^2 - N$로 분할했습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int cnt = 0;

set<p> st;

void dfs(ll n){
    ll x = sqrt(n);
    if(n != x*x) x++;
    ll y = x*x - n;
    if(x > 2) dfs(x);
    if(y > 2) dfs(y);
    if(!st.count({x, y})){
        cnt++;
        cout << x << " " << y << "\n";
        st.insert({x, y});
    }
}

int main(){
    ll n; cin >> n;
    dfs(n);
    assert(cnt <= 43);
}