baekjoon #1193_분수찾기

#include <iostream>
using namespace std;

int main() {
    int X;
    cin >> X;
    int idx = 1;
    int diff = 0;
    for (int add = 0; add + idx < X; idx++)
    {
        add += idx;
        diff = X - add;
    }
    if (idx == 1)
        cout << "1/1";
    else if (idx % 2 == 0)
        cout << diff << "/" << idx - diff + 1;
    else
        cout << idx - diff + 1 << "/" << diff;
    return 0;
}

 

idx	idx번째 지그재그의 분수들
1	1/1
2	1/2, 2/1
3	3/1, 2/2, 1/3
4	1/4, 2/3 ,3/2, 4/1
...	...

 

일반화 하면,

idx 가 1일 경우, 1/1

idx 가 홀일 경우,  idx/1, (idx - 1)/2, (idx - 2)/3, (i - 3)/4, ...

idx 가 짝일 경우,  1/idx, 2/(idx - 1), 3/(idx - 2), 4/(i - 3), ...

 

분수 m / n

 

X  ->  구하고자하는 분수가 몇 번째에 있는지 나타내기 위해 입력받는 수 ( X 번째 분수를 구하는 것 )

idx  ->  몇 번째 지그재그인지 나타내는 수

idx - diff + 1  ->  idx가 홀일 경우 m을 나타내기 위해 필요, idx가 짝일 경우 n을 나타내기 위해 필요

 

for문 안에 있는

조건 add + idx < X

add  ->  add = 0 으로 시작해서 add (0) + idx (몇 번째 지그재그인지) < X번째

   idx 가 1일 때, add = 0 + 1 = 1

   idx 가 2일 때, add = 1 + 2 = 3

   idx 가 3일 때, add = 3 + 3 = 6

   idx 가 4일 때, add = 6 + 4 = 10

   ...

diff = X - add  ->  X번째 - add 

   idx 가 1일 때, diff = X - 1

   idx 가 2일 때, diff = X - 3

   idx 가 3일 때, diff = X - 6

   idx 가 4일 때, diff = X - 10

   ...

 

=> idx 가 홀일 경우, m = idx - diff + 1   /   n = diff

=> idx 가 짝일 경우, m = diff   /   n = idx - diff + 1

 

idx	m / n	1 : 1/1 홀 : idx/1, (idx - 1)/2, (idx - 2)/3, ... 짝 : 1/idx, 2/(idx - 1), 3/(idx - 2), ...
1	1 / 1	1 / 1
2	1 / 2	1 / 2
	2 / 1	2 / (2 - 1)
3	3 / 1	3 / 1
	2 / 2	(3 - 1) / 2
	1 / 3	(3 - 2) / 2
4	1 / 4	1 / 4
	2 / 3	2 / (4 - 1)
	3 / 2	3 / (4 - 2)
	4 / 1	4 / (4 - 3)
5	5 / 1	5 / 1
	4 / 2	(5 - 1) / 2
	3 / 3	(5 - 2) / 3
	2 / 4	(5 - 3) / 4
	1 / 5	(5 - 4) / 5

 

ex) 9

X = 9

idx	add += idx	diff = X - add	idx++	add + idx < X
1	add = 0 + 1 = 1	diff = 9 - 1 = 8	2	1 + 1 < 9  ->  true
2	add = 1 + 2 = 3	diff = 9 - 3 = 6	3	3 + 2 < 9  ->  true
3	add = 3 + 3 = 6	diff = 9 - 6 = 3	4	6 + 3 < 9  ->  false

idx=1	idx=2	idx=3	idx=4
1	2	6	7
3	5	8	...
4	9	...	...
10	...	...	..

=> idx = 4  ->  4번째 지그재그의 분수임을 알 수 있음

분수를 m / n 으로 표기할 때,

=> idx가 4 이므로,  m = diff = 3   /   n = idx - diff + 1 = 4 - 3 + 1 = 2

 

X번째 분수는 3 / 2 임을 알 수 있음

 

 

• 다른 풀이

#include <iostream>
using namespace std;

int main() {
    int X, idx;
    cin >> X;
    for (idx = 1; idx < X; idx++) {
        X -= idx;
    }
    if (idx % 2 == 0)
        cout << X << "/" << idx + 1 - X;
    else
        cout << idx + 1 - X << "/" << X;

    return 0;
}

ex) 8

X = 8

홀 : (idx + 1 - X) / X
짝 : X / (idx + 1 - X)

idx	idx < X	X -= idx	idx++
1	1 < 8  ->  true	X = 8 - 1 = 7	2
2	2 < 5  ->  true	X = 7 - 2 = 5	3
3	3 < 5  ->  true	X = 5 - 3 = 2	4
4	4 < 2  ->  false

=> idx = 4  ->  짝 -> X / (idx + 1 - X)

=> 2 / (4 + 1 - 2)

=> 2 / 3