백준 1193번: 분수찾기

백준 1193번: 분수찾기

1193번: 분수찾기

 

2차원 배열인데 시간 제한이 0.5초이네? 이것을 보자마자 간단한 규칙으로 풀 수 있을 것 같은 생각이들어서 규칙을 먼저 찾기 시작했다. 난 규칙을 찾는 기준을 1번째 3번째 6번째 10번째 15번째 위치에있는 분수들로 잡았다. 저 분수들은 다 테두리에 있는 분수들이다. 이 분수들의 표를 1/1가 꼭대기인 삼각형 모양으로 만들었을 때 1/1(1번)은 1번째 2/1(3번)는 2번째 1/3(6번)은 3번째 4/1(10번)은 4번째줄에 나타나는 것을 확인했다. 이것을 보아 홀수번째 줄과 짝수번째 줄에 있을 때 내가 고른 분수들이 삼각형 기준 맨 좌측에 있냐 맨 우측에 있냐로 나뉘었다. 만약 8번째 위치의 숫자를 찾는다면 10번째 위치인 4/1이고 10 - 8인 2를 4/1에서 분자에서 빼고 분모에 더해 10번째 숫자를 구했다.

 

#include<iostream>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int x;
    cin >> x;
    //1:1/1 3:2/1 4:3/1 10:3/1 11:4/1 21:5/1...
    int sum = 0;
    int cnt = 0;
    for(int i = 1; sum < x; i++){
        cnt += 1;
        sum += i;
    }
    int t = sum - x;
    if(cnt % 2 != 0){
        cout << 1+t <<"/"<< cnt-t;
    }else{
        cout << cnt-t <<"/"<< 1+t;
    }
    return 0;
}