[BOJ] 1193번 : 분수찾기

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int x; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> x;
	int n = 0;
	while ((n * (n + 1) / 2) < x) n++;
	int row, col;
	int sum = (n * (n + 1)) / 2; 
	int diff = sum - x;
	if (n % 2 == 0) {
		row = n - diff; 
		col = 1 + diff;
	}
	else {
		row = 1 + diff; 
		col = n - diff;
	}
	cout << row << '/' << col << '\n';
}

1~n까지의 자연수합으로 n을 결정한 다음, 규칙을 이용해서 diff를 더하거나 빼줬다.

 

3. solution 2 :

// Authored by : SciEm
// Co-authored by : -
// http://boj.kr/4786afbccbb148098938f248823abd35
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int x;
  cin >> x;

  // x에서 1 2 3 ...을 빼다보면 찾는 수가 i 번째 군의 x 번째 수가 된다.
  int i = 1;
  while (x > i) {
    x -= i;
    i++;
  }

  int nume = x;
  int deno = i + 1 - x;
  if (i % 2) swap(nume, deno);  // 홀수 번째 군의 순서가 문제와 반대이므로 뒤집는다.
  cout << nume << '/' << deno;
}
/*
수열을 (1/1) (1/2 2/1) (1/3 2/2 3/1) ... 과 같이 묶으면 i번째 군의 개수는
i개 이고 분자와 분모의 합이 i + 1로 일정함을 알 수 있다.
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/1193.cpp

basic-algo-lecture/0x12/solutions/1193.cpp at master · encrypted-def/basic-algo-lecture

합이 일정하다는 것을 이용했다는 점과 swap을 이용해 규칙을 이용했다는 점과 while문을 이용해 x와 i값을 결정했다는 점이 흥미롭다.