[백준] 알고리즘 1193번 - 분수찾기문제

문제

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int x;
	cin >> x;
	int i = 1;
	while (x > i) {
		x -= i;
		i++;
	}
	if (i % 2 == 1) cout << i + 1 - x << "/" << x;
	else cout << x << "/" << i + 1 - x;
}

해설

계속해서 대각선 끝과 끝까지 내려갓다 올라갓다를 반복하는 순서를 찾을 수 있습니다.

여기서 우리는 규칙을 찾아봐야합니다.

짝수번째일때는 대각선이 위에서 아래로 향하는 순서로 되어있다.

홀수번째일때는 대각선이 아래에서 위로 향하는 순서로 되어있다.

 

이로써 나열하여 분모와 분자의 규칙을 찾을 수 있다.

i번째의 행렬에 x가 포함하는지 알아야한다. 이것은 i번부터 차례대로 x값을 빼주면서 i가 x보다 커질때 이 수는 i번째에 포함된다고 볼 수 있다.

 

그렇다면 이 i번째를 저장해놓고 홀수인지 짝수인지 판단하여 규칙을 적용시킨다.