1011(다른 방법으로 꼭 다시 풀어 보기)

내가 생각한 접근 방법

while(T--)

    {

        int k = 1,tmp=0,cnt=0;

        int kn[3] = {0,};

        cin>>x>>y;

        tmp = x + k;

        cnt += 1;

        while(tmp == y-1)

        {

            if(k==1) {kn[0] = 0; kn[1] = 1; kn[2] = 2;}

            else

            {

                kn[0] = k-1; kn[1] = k; kn[2] = k+1;

            }

            //Todo.

        }

    }

큰 숫자를 우선적으로 작동시키고 만약 Kn의 값 범위에서 진행하다가 Y-1 에 도달할 수 없을 경우 다시 되돌아가 K의 값을 차감하고 모든 경우를 탐색? 해보려 하였으나 여기서 더이상 진행시킬 엄두가 나지 않는다. 매운 더러운 스파게티 코드가 나올게 뻔하다. 

(물론 BF나 다른 방법으로도 풀 수 있을듯하나 아직 실력이 되지 않으니 해답을 참고해서 규칙을 이해하는 것으로!)

다음과 같은 규칙을 가지고 있다고 한다. 상상도 하지 못했다. 문제를 접근하는 방법을 달리 해야할 필요가 있겠다. kn = k-1, k, k+1 +1 여기서만 머리가 맴돌고만 있었다.

#include <iostream>

using namespace std;

int main()

{

    int x,y,T;

    cin>>T;

    while(T--)

    {

        long long n, minN, powN, maxN, cnt=0;

        cin>>x>>y;

        for(n=1;;n++)

        {

            powN = n*n;

            minN = powN - n + 1;

            maxN = powN + 1 + n - 1;

            if(minN <= y-x && y-x <= maxN )

            {

                if(minN <= y-x && y-x <= powN) cnt = (n<<1)- 1;

                else cnt = n<<1;

                break;

            }

        }

        cout<<cnt<<endl;

    }

    return 0;

}

BF나 DP 쪽을 공부하고 반드시 다시 풀어봐야겠다.

[참고 : http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220982644540&categoryNo=0&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView]