[백준 알고리즘/BOJ/C++] 1193 분수찾기

 

 

이거 풀 때 지그재그를 잘못 이해해서 개고생 했던 기억이 난다..

암튼 위와 같은 지그재그 순서로 배열을 읽을 때, n번째 분수는 무엇인지 출력하면 된다

 

이렇게 대각선으로 1, 2, 3 ··· 번호를 매겨보자 (1씩 증가하는 등비수열)

이 번호가 홀수일 때는 ↙ 이 방향으로 숫자를 세고, 짝수일 때는 ↗ 이렇게 센다

 

이걸 캐치하면 쉬워진다

 

 

#include <iostream>
using namespace std;
 
int main()
{
    int n, cnt = 0;
    cin >> n;
 
    while (n > 0)
    {
        cnt++;
        n -= cnt;
    }
 
    if (cnt % 2 == 0)
        cout << cnt + n << "/" << 1 + (-n);
    else
        cout << 1 + (-n) << "/" << cnt + n;
}

 

cnt는 n번째 분수가 몇 번째 대각선에 속해있는지 count 한다고 보면 된다

n에서 cnt를 계속 빼주면 어느 시점에서 0과 같거나 작아질 때가 있다

그때의 cnt와 n으로 분수를 구할 수 있다

 

n = 14 일 때

14 - 1 = 13

13 - 2 = 11

11 - 3 = 8

8 - 4 = 4

4 - 5 = -1

 

cnt는 5, n은 -1이 된다 → 5번째 대각선 +1 번째에 있다

분모는 cnt에서 n을 더한 값, 분자는 (-n)에서 1을 더한 값인걸 확인할 수 있다!

(대각선의 마지막은 n이 0일 때 인걸 인식하고 있으면.. 쉽게 유추 가능)

cnt가 짝수일 땐 홀수와 반대로 수를 세니까 분자/분모 식을 바꿔서 출력하면 된다