백준, BOJ, 1011번, Fly me to the Alpha Centauri : C++ [CPP]

 

어렵다기보다..

수학으로 풀면 규칙 찾아내는 것이지만

다이나믹 프로그래밍 분류에 있어서

뭐 그렇게 풀려고 했으나..내 머리가 모자라서..

 

 

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

1011번: Fly me to the Alpha Centauri

 

 

---

 

우선 다이나믹프로그래밍으로 풀려고하는 방법은

큰 문제를 작은 문제로 쪼개는 것이다.

때문에

x부터 y라면

x 부터 y-1까지 가는 방법에서 y-1에 2로 도착하는 방법과 y-1에 1로 도착하는 방법이 있으니

이것을 잘 활용하면 될 것 같은데..

포기하고 수학으로 풀었다.

#include <iostream>
#include <cmath>

using namespace std;
using ll = long long;
int n;


void init(){
    cin.tie(0);
    ios::sync_with_stdio(0);
}

ll func(ll x, ll y){
    ll dist = y-x;
    ll k = sqrt(dist);
    //제곱수이면, 16이라면 4+3의 개수를 가짐
    if(k*k == dist)return(2*k-1);
    else{
        //아니면 그 사이의 범위를 나눠야함
        //제곱수 사이의 숫자는 항상 짝수이다 9~16 -> 10,11,12   13,14,15
        
        //부연 설명하자면 3^2은 5개를 가진다.
        //3^2 과 4^2 사이에는 6개가 있다.
        //-> k^2와 (k+1)^2 사이에는 2*k개가 있다.
        
        //생각해보면 당연히 곱셈공식으로 빼면 2k개가 나오는 것은 당연하고
        //k^2 ~ k^2+k 까지는 같은 개수를 갖게되고
        //k^2+k ~ (k+1)^2 까지도 같은 개수를 갖게 된다.
        //하다 보면 규칙을 찾는다.
        

        ll p = 2*k - 1;
        if(dist<= k*k+k){
            // ex) 12라면 3의 제곱인 9가 가지는 개수보다 하나 많음 (2k-1 + 1)
            return p+1;
        }else{
            //15라면 3의 제곱인 9가 가지는 개수보다 두 개 많음 (2k-1 + 2)
            return p+2;
        }
    }
    
}

int main(){
    init();
    cin >> n;

    
    
    for(int i = 0; i<n; i++){
        ll a, b;
        cin >> a >> b;
        ll ans = func(a,b);
        cout << ans << "\n";
    }
}

 

설명은 다 주석과 같이 달아놓았다.

16까지만 하나하나 세어보자