Problem C 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1560/problem/C












채워지는 수들 중 가장 윗줄의 수가 채워지는 규칙을 보면,

1  2 (+1)  5 (+3)  10 (+5) ~~ 이런 식이다. 더해지는 수를 d라고 한다면 더해지는 수 d가 한번 더해질 때마다 +2씩 늘어난다.

이 윗줄의 수를 계산해서 a <= k < a + d인 a를 찾는다.

1   2   5   10   ~~   a   a+d 이런 구성이다.

여기서 a의 r = 1, c = ( a까지 채워진 숫자의 개수 ) 가 된다.

숫자가 채워지는 규칙이 윗줄의 수부터 행렬을 둘러싸는 규칙이기 때문에

a의 r, c를 아는 상태로 k에 대해서 r, c의 값을 찾는 규칙은 아래와 같다.

if ( k <= a + d/2 ) -> r = 1 + (k - a), c = c

else if ( k > a + d/2 ) -> r = 1 + d/2, c = c - ( k - ( a + d/2 ) )


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
#include <iostream>
 
using namespace std;
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        int k;
        cin >> k;
 
        int r = 1, c = 1;
        int d = 1;
        int num = 1;
 
        while (!(num <= k && k < num + d)) {
            c++;
            num += d;
            d += 2;
        }
 
        if (k <= num + d / 2)
            cout << r + k - num << " " << c << endl;
        else
            cout << d / 2 + 1 << " " << c - (k - (num + d / 2)) << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기