티스토리 뷰
2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8891에서 채점할 수 있습니다.
요약 )
이 문제는 '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현하면 해결할 수 있습니다. 이 두 함수를 구하기 위해선 점 숫자의 특징을 잘 관찰해야 합니다. 점 숫자의 가장 큰 특징으로는 같은 대각선일 경우, 점 숫자가 하나 늘어날 때 마다 x++, y-- 가 된다는 점이 있습니다. 이 점을 최대한 활용하기 위해 '대각선 시작 지점의 점 숫자'들을 저장한 배열을 만들면 '점 숫자로 x, y 좌표 구하는 함수'와 'x, y 좌표로 점 숫자를 구하는 함수' 를 구현할 수 있습니다.
x=1 일 때(대각선 시작 지점) 점 숫자 구하기 )
1 2 3 4 5 6 7 | // 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); } | cs |
st[1] = 1임은 당연합니다. 첫 번째 대각선은 (1,1) 만 포함하므로 st[2] = 2 가 되는 것도 당연합니다. 그 다음부터는 대각선의 길이가 2, 3, 4, 5 이런 식으로 늘어나므로 st[i] = st[i-1]+i-1 의 점화식이 성립합니다.
점 숫자로 x, y 좌표 구하기 )
1 2 3 4 5 6 7 | // 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); } | cs |
위와 같이 이분 검색을 돌리면, 'st[idx] = v이하인 대각선의 시작 지점 점 숫자 중 최대값'이 되는 idx를 찾을 수 있습니다.
그러면 (1, idx) = st[idx] 의 식이 성립하면서 동시에 v가 st[idx]부터 시작하는 대각선 위에 있음을 알 수 있습니다. 이제 같은 대각선일 경우, 점 숫자가 하나 늘어날 때 마다 x++, y-- 가 된다는 점을 이용하여 x, y 좌표를 구할 수 있습니다.
x, y 좌표로 점 숫자 구하기 )
1 2 3 4 | // code by RiKang, weeklyps.com long long get_value(int x, int y){ return st[x+y-1] + x - 1; } | cs |
(x, y) 가 속한 대각선의 시작 지점은 (1, x+y-1) 입니다. 점 숫자로는 st[x+y-1] 이 되며 이 지점에서 x-1만큼 이동하였으므로 위와 같이 점 숫자를 구할 수 있습니다.
최종 코드 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | // 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; } | cs |
'문제 풀이' 카테고리의 다른 글
[BOJ 8893] Pandora (0) | 2018.01.11 |
---|---|
[BOJ 8894] Pattern Lock (0) | 2018.01.11 |
[BOJ 8895] 막대 배치 (0) | 2018.01.10 |
[BOJ 8896] 가위 바위 보 (0) | 2018.01.09 |
[BOJ 8892] 팰린드롬 (0) | 2018.01.09 |