백준 1193번 (C++)

www.acmicpc.net/problem/1193

1193번: 분수찾기

 

<답안>

#include <iostream>

using namespace std;

int main() {

    int x;

    int temp = 1;

    int i = 1;

    int n = 1,m = 1;

    

    cin>>x;

    while(x > temp)

    {

        i++;

        temp+=i;

    }

    if(i%2 == 0)

    {

        n = i;

        m = 1;

        n = n - (temp-x);

        m = m + (temp-x);

    }

    else

    {

        n = 1;

        m = i;

        n = n + (temp-x);

        m = m - (temp-x);

    }

    cout<<n<<"/"<<m;

    return 0;

}

 

<설명>

이문제 역시 규칙을 먼저 찾고서 시작하였다

1번째 : 1/1 -> 2를 더한다 (i=1 -> i=2)

3번째 : 2/1 [왼쪽끝] -> 3을 더한다 (i=2 -> i=3)

6번째 : 1/3 [오른쪽끝] -> 4를 더한다 (i=3 -> i=4)

...

식으로 1부터 차례로 2,3,4를 더한 번째가 대각선 방향의 끝지점임을 알 수 있었다

여기에 네가지 규칙이 더해지는데

1. 더할 i 값이 2,3,4씩 차례로 1씩 증가한다

2. 증가된 i값이 분모, 또는 분자에 해당되는 값이다

3. i가 짝수인 경우 왼쪽 끝이며, i값이 분자에 해당되고,

    입력된 x와 누적계산된 temp간의 차액만큼 분자는 감소, 분모는 1부터 증가한다

4. i가 홀수인 경우 오른쪽 끝이며, i값이 분모에 해당되고,

    입력된 x와 누적계산된 temp간의 차액만큼 분자는 1부터 증가, 분모는 감소한다

 

이러한 규칙을 토대로

입력된 x가 누적계산된 temp보다 클경우 i 증가, temp 누적하며 i값을 찾는다

i값의 홀,짝 여부에 따라 분모, 분자를 정한 뒤, 차액만큼 빼고 더하여

각각의 분모, 분자 값을 찾는다