[백준 / BOJ] - 1193번 분수찾기 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [1193] 

https://www.acmicpc.net/problem/1193

문제

 

 

위와 같은 지그재그로 순서를 할당하는 배열이 있다. 입력으로 순서 X가 주어졌을 때, X 번째 분수를 구하는 프로그램을 작성하는 문제이다.

 

풀이

 

규칙을 찾아서 풀어야 하는 문제이다. 1/1, 1/2, 2/1, 3/1, 2/2, 1/3 식으로 지그재그의 한 패턴당 1개, 2개, 3개식으로 늘어난다.

즉 입력받은 숫자가 몇번째 지그재그 패턴인지 먼저 찾아야 한다. 그 후, 해당 지그재그 패턴에서 몇번째 수인지를 알면 분수를 구할 수 있다.

 

짝수번째 패턴의 경우에는 1/i, 2/(i-1),3/(i-2), ..., i/1식으로 진행이 되고

홀수번째 패턴의 경우에는 i/1, (i-1)/2, (i-2)/3, ..., 1/i식으로 진행이 된다.

 

위와 같은 일반화된 공식을 활용하여 코드를 작성하면 반복문을 최소로 사용하면서 풀 수 있다.

 

코드

 

#include <iostream>
using namespace std;
int main() {
    int idx;
    cin >> idx;
    int i = 1;
    int diff = 0;
    for(int sum = 0; sum+i < idx; i++)
    {
        sum += i;
        diff = idx - sum;
    }
    if(i%2 == 1)
        cout << i-diff+1 << "/" << diff;
    else
        cout << diff << "/" << i-diff+1;
    return 0;
}

 

평가

 

반복문을 사용하면서 지그재그수를 하나하나 다 계산하다보면, 시간 초과가 발생하는 문제이다.

일반화된 규칙을 찾아내고, 주어진 변수를 활용하여 바로 계산하는 식으로 문제를 풀어야 한다.