728x90
반응형
1193번: 분수찾기
문제
https://www.acmicpc.net/problem/1193
풀이
나열된 분수는 1/1, 1/2, 2/1, 3/1, 2/2, 1/3,... 과 같은 순서로 이루어져 있다. 순서대로 1번, 2번, 3번,... 분수라고 할 때, X번째 분수를 구하는 문제다.
표에서 대각선마다 규칙이 있는데 홀수번째 줄은 위로, 짝수번째 줄은 아래로 향한다. 또 N번째 줄에는 N개의 분수가 있다.
따라서 X번째 수가 있는 줄까지 가기 위해 X에서 각 줄마다 있는 분수의 수만큼 빼주다가(X -= line) 더 이상 뺄 수 없을 때까지 줄을 이동한다.
그리고 홀수번째 줄일 때는 아래에서부터 시작이고, 짝수번째 줄일 때는 위에서부터 시작이므로 각 줄의 출발지점으로부터 분자는 X번째 수다. 따라서 홀수번째 줄일 때는 분자는 line - X + 1이고 분모는 X, 짝수번째 줄에서는 분자가 X이고 분모가 line - X + 1이다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int x;
cin >> x;
int line = 1;
while (x > line) {
x -= line;
line++;
}
if (line % 2)
cout << line - x + 1 << '/' << x << '\n';
else
cout << x << '/' << line - x + 1 << '\n';
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 27465 소수가 아닌 수 (0) | 2023.02.12 |
---|---|
[백준 / BOJ] C++ 27445 Gorani Command (0) | 2023.02.11 |
[백준 / BOJ] C++ 1181 단어 정렬 (0) | 2023.02.11 |
[백준 / BOJ] C++ 1158 요세푸스 문제 (0) | 2023.02.11 |
[백준 / BOJ] C++ 1157 단어 공부 (0) | 2023.02.11 |