백준 1011번 (C++)

www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

<답안>

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    int t;

    unsigned int x, y, term;

    int afterMath;

    int result = 0;

    int temp;

    cin>>t;

    while(t-- > 0)

    {

        cin>>x>>y;

        term = y-x;

        afterMath = sqrt(term);

        

        if(term == afterMath*afterMath)

        {

            result = 2*afterMath-1;

        }

        else

        {

            temp = afterMath*afterMath + afterMath;

            if(term <= temp)

            {

                result = (2*afterMath-1) + 1;

            }

            else

            {

                result = (2*afterMath-1) + 2;

            }

        }

        cout<<result<<"\n";

    }

    

    return 0;

}

 

<설명>

이 문제가 개인적으로 지금까지의 백준문제중 가장 어려웠던 문제였던거 같다

문제를 이해하는데도 시간이 걸렸으며 어떻게 풀어야할지 고민하는데도 많이걸렸다

이런문제를 풀때 하나하나 적어보며 규칙을 먼저 찾고서 시작한다

일단 이렇게 쭉 나열을 해봤다

여기서 뭔가 혹시? 라고 느껴졌던 포인트가 두가지가 있었다

1. 하나는 입력된 거리값이 제곱수인 경우 (1,4,9,16 등등)

제곱수를 루트처리한 값 (1,2,3,4 등등)까지 차례로 증가했다가 떨어지는 경우를 볼 수 있었다 (16 : 1234321)

2. 다른하나는 점프수값이 한번, 한번, 두번, 두번, 세번, 세번 등등

두번씩 반복되면서 증가되는 모습이 보였다

 

그렇게 어렴풋이 규칙을 가지고서 다시 고민을 해보았다

역시나 더 많은숫자를 비교해보아도 규칙이 일치하는 모습이 보였다

 

입력된 숫자를 루트값을 계산하여 구해진 afterMath 값을 기준으로

만약 입력값이 afterMath의 제곱이면

결과값 result = 2 * afterMath - 1 이다

그 외의 경우, 즉 입력값이 afterMath의 제곱보다 큰 경우는 두가지로 나뉜다

1. 위에서 구한 result + 1인 경우

2. 위에서 구한 result +2인 경우

 

1의 경우는 afterMath 값의 제곱수 (4라면 16) + afterMath 값 (4) 까지가 +1이다

2의 경우는 그 외의 경우이고, +2를 하여 구하면 된다

 

그렇게 구해진 result 값을 출력하면 된다