Codeforces Round #739 (Div. 3)-C. Infinity Table

문제 설명

재혁은 무한개의 수가 적혀있는 표를 가지고 있다. 이 표의 행과 열 모두 1부터 시작한다.

표의 초기상태는 아무것도 적혀있지 않다. 그 이후 좌상단에 1을 적으면서 시작한다. 그 이후 표에는 다음과 같은 방식으로 수를 적어나간다.

재혁의 친구는 자신이 가장 좋아하는 숫자 $k$를 가지고 있다. 그는 이 수가 재혁이 가지고 있는 표에서 어느 위치에 있는지 알고 싶다. 재혁이의 친구가 $k$가 위치한 행과 열을 찾을 수 있게 도와주자.

Input
첫번째 줄에는 테스트 케이스의 수 $t(1\le t\le {10}^4)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 위치를 반드시 찾아야 하는 정수 $k(1\le k\le {10}^9)$ 가 주어진다.

Output
각 테스트케이스마다 표에서 $k$가 위치하고 있는 행과 열을 각각 공백을 기준으로 정수 $r$과 $c(r,c\ge 1)$ 을 출력한다.

Example
input
7
11
14
5
4
1
2
1000000000

output
2 4
4 3
1 3
2 1
1 1
1 2
31623 14130

문제 접근

사용한 알고리즘: 수학
걸린 시간 : 00:09
프로그래머가 알고리즘을 공부할 때 수학이 왜 필요한지를 깨닫게 해준 나머지 문제 set이다.

여기서 관찰해 보아야 할 것은 가장 좌측 열인 1번째 열이다. 각 열에 위치한 수는 $i$번째 행이라고 했을 때, $i\ast i$로 표현 할 수 있다. 그렇다면 이 수를 기준으로 _|모양을 하나의 라인이라고 생각하자. 그러면 그 라인에 있는 수들은 $\sqrt{n}$ 을 올림 처리하면 모두 같은 $i$라는 수가 나온다.

그렇다면 이 모양의 우측 하단 꼭짓점에 있는 수는 어떻게 구할 수 있을까? 이 수는 _|모양에 가운데 수이기 때문에 구하면 좌표값을 편하게 구할 수 있다. 각 모양의 가장 왼쪽에 있는 수는 $i$번째 행이라고 할 때, $i\ast i$이다. 이 값에 $i-1$을 뺀다면 가운데 수를 구할 수 있다.

주어진 수$n$이 가운데 값인 $m$보다 크면 _모양의 왼쪽에 위치하기 때문에 행은 가만히 두고, 열 값을 변화한다.
주어진 수$n$이 가운데 값인 $m$보다 작으면 |모양의 위쪽에 위치하기 때문에 열은 가만히 두고, 행 값을 변화한다.

정답 코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int k = ceil(sqrt(n));
        int m = k * k - (k - 1);
        if(m < n) cout << k << " " << k - abs(m - n);
        else cout << k - abs(m - n) << " " << k;
        cout << "\n";
    }
    return 0;
}