백준 1193번: 분수찾기 [C++]

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

1193번: 분수찾기

코드

#include <iostream>
using namespace std;

int main(){
  int n;
  cin >> n;

  int i = 1;
  while(n - i > 0){
    n -= i;
    i++;
  }

  if(i%2){
    cout << i - (n - 1) << "/" << n;
  }
  else{
    cout << n << "/" << i - (n - 1);

  }

}

 

풀이

규칙을 찾는것이 항상 중요하다.

주어진 문제를 이렇게 대각선으로 잘라서 보자

첫 번째 줄에는 1/1 1개가 있고

두 번째 줄에는 1/2 , 2/1 2개가 있다.

세 번째, 네 번째 줄에는 당연히 3개, 4개가 있을것이다.

그렇다면 간단하다, 5번째 분수에 대해 생각해보자.

 

1) N 번째 줄에 위치해 있을까?

3번째 줄이다.

 

2) 그 줄에서 M 번째에 위치해 있을까?

2번째다.

 

3) N이 홀수인가 짝수인가?

홀수이다.

홀수이면 순서가 지나갈수록 분자는 1씩 감소하고 분모는 증가하므로

(N - 1) / M => 2/2  가 답이 된다.

 

이를 생각해서 알고리즘을 구성하면 될 것 같다.