[SWEA] 4112 이상한 피라미드 탐험

 

오늘부터 SWEA 문제를 풀어보기로 했다!

처음으로 풀어본 문제다! 수학적인 문제라고 생각하는데 생각도못하고 오~~래 틀렸다

 

이 문제는 부분합으로 배열을 구하면 각 층을 index라 생각할 수 있고

층에있는 수의 갯수를 psum[index] 라고 생각 할 수 있다

 

두 수 a,b가 들어왔을 때 우리는 무조건 작은수에서 큰수로 갈 것이다

그럼 위에서 아래로 내려오면 되는데 이때 삼각형을 정삼각형으로 l,r 두 방향으로 내려온다

 

현재 dep에서의 index를 사용하면 l,r을 구하기 쉽다!

dep는 lower_bound를 통해 구하면 된다

 

기본적으로 무조건 dep차이만큼은 가야한다!

큰 수와 같은 dep까지 왔을 때가 중요하다!

 

1) l<maxn 이라면 정삼각형 범위보다 안쪽에 있으므로 +(maxn-l)

2) maxn<r 이라면 +(r-maxn)

 

만큼 더해주면 된다!

 

만약 그 사이의 범위라면 dep차이가 답이다

두 개의 점을 포함하는 정삼각형을 그려보면 무조건 한 변의 길이로 갈 수 있다!

 

이상한 피라미드속의 삼각형이였다..!! 

 

간만에 하니 어렵다..!!

 

[소스코드]

#include <iostream>
#include <algorithm>
using namespace std;
int psum[222];
 
int depth(int num){
    return lower_bound(psum,psum+200,num) - psum;
}
 
int main(){
    for(int i=1;i<=200;i++) psum[i] = psum[i-1]+i;
    int tc; scanf(" %d",&tc); int c=1;
    while(tc--){
        int a,b; scanf(" %d %d",&a,&b);
        int maxn = max(a,b), minn = min(a,b);
        int dep = depth(minn), target = depth(maxn);
        if(dep == target) printf("#%d %d\n",c++,abs(maxn - minn));
        else {
            int index = psum[dep] - minn;
            int ans = target - dep;
            int r = psum[target] - index;
            index = dep - index;
            int l = psum[target-1] + index;
            if(maxn>r) ans+=(maxn-r);
            if(maxn<l) ans+=(l-maxn);
            printf("#%d %d\n",c++,ans);
        }
    }
}