[BOJ 8891] 점 숫자

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8891에서 채점할 수 있습니다.

요약 )

 이 문제는 '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현하면 해결할 수 있습니다. 이 두 함수를 구하기 위해선 점 숫자의 특징을 잘 관찰해야 합니다. 점 숫자의 가장 큰 특징으로는 같은 대각선일 경우, 점 숫자가 하나 늘어날 때 마다 x++, y-- 가 된다는 점이 있습니다. 이 점을 최대한 활용하기 위해 '대각선 시작 지점의 점 숫자'들을 저장한 배열을 만들면  '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현할 수 있습니다.

x=1 일 때(대각선 시작 지점) 점 숫자 구하기 )

// code by RiKang, weeklyps.com
void get_st(){
    st.push_back(0);
    st.push_back(1);
    for(int i=1; i<=25000; i++)
        st.push_back(st.back()+i);
}

  st[1] = 1임은 당연합니다. 첫 번째 대각선은 (1,1) 만 포함하므로 st[2] = 2 가 되는 것도 당연합니다. 그 다음부터는 대각선의 길이가 2, 3, 4, 5 이런 식으로 늘어나므로 st[i] = st[i-1]+i-1 의 점화식이 성립합니다.

점 숫자로 x, y 좌표 구하기 )

// code by RiKang, weeklyps.com
PII get_xy(long long v){
    int idx = upper_bound(st.begin(),st.end(),v) - st.begin() - 1;
    int x = v-st[idx]+1;
    int y = idx-(v-st[idx]);
    return PII(x, y);
}

 위와 같이 이분 검색을 돌리면, 'st[idx] = v이하인 대각선의 시작 지점 점 숫자 중 최대값'이 되는 idx를 찾을 수 있습니다.

 그러면 (1, idx) = st[idx] 의 식이 성립하면서 동시에 v가 st[idx]부터 시작하는 대각선 위에 있음을 알 수 있습니다. 이제 같은 대각선일 경우, 점 숫자가 하나 늘어날 때 마다 x++, y-- 가 된다는 점을 이용하여 x, y 좌표를 구할 수 있습니다.

 x, y 좌표로 점 숫자 구하기 )

// code by RiKang, weeklyps.com
long long get_value(int x, int y){
    return st[x+y-1] + x - 1;
}

 (x, y) 가 속한 대각선의 시작 지점은 (1, x+y-1) 입니다. 점 숫자로는 st[x+y-1] 이 되며 이 지점에서 x-1만큼 이동하였으므로 위와 같이 점 숫자를 구할 수 있습니다.

최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - D
// BOJ 8891 점 숫자
 
#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace::std;
 
vector<long long> st;
 
 
void get_st(){
    st.push_back(0);
    st.push_back(1);
    for(int i=1; i<=25000; i++)
        st.push_back(st.back()+i);
}
 
PII get_xy(long long v){
    int idx = upper_bound(st.begin(),st.end(),v) - st.begin() - 1;
    int x = v-st[idx]+1;
    int y = idx-(v-st[idx]);
    return PII(x, y);
}
long long get_value(int x, int y){
    return st[x+y-1] + x - 1;
}
 
void solve(){
    int v1, v2;
    scanf("%d %d",&v1,&v2);
    PII xy1 = get_xy(v1);
    PII xy2 = get_xy(v2);
    printf("%lld\n",get_value(xy1.first+xy2.first, xy1.second+xy2.second));
}
 
int main(){
    get_st();
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}