https://www.acmicpc.net/problem/1193
규칙성을 찾는데 조금 애먹었다. 군수열에 관한 문제였다.
1/1 | 1/2 | 1/3 | 1/4 | 1/5 | … |
2/1 | 2/2 | 2/3 | 2/4 | … | … |
3/1 | 3/2 | 3/3 | … | … | … |
4/1 | 4/2 | … | … | … | … |
5/1 | … | … | … | … | … |
… | … | … | … | … | … |
1/1 → 1/2 → 2/1 → 3/1 → 2/2 → …순서인데 우상단→좌하단방향으로 잘라보면(위의 표에서)
1/1 // 1/2, 2/1 // 3/1, 2/2, 1/3 // 1/4, 2/3, 3/2, 4/1 // ...의 수열을 얻을 수 있다. //를 기준으로 1/1부터 1군이라고 하자.
n군에 대해서 n이 홀수이면 분자가 n부터 1까지, 분모가 1부터 n까지 증가하고, n이 짝수이면 그 반대의 규칙을 보인다.
또한 n군의 k번째 요소는 전체 수열에서 그 위치가 다음과 같다.
이러한 점들을 코드에 반영하자.
일단 주어진 숫자가 몇번째 군의 몇번째 요소인지 판별을 한 후에, 그 군이 짝수번째군이냐, 홀수번째 군이냐에 따라 나누어서 출력해주었다.
#include <stdio.h>
int which_group (int num, int * group) {
int idx = 1; // 몇번째 군에 속한지 계산하기 위함
while (1) {
/* 등차수열의 합 공식을 이용해 몇번째 군인지 찾는다. 조건식 더러움 주의 */
if (idx * (idx - 1) / 2 <= num && idx * (idx + 1) / 2 >= num) {
break;
} else {
idx++;
}
}
*group = idx; // 몇번째 군에 있는지
return num - (idx * (idx - 1) / 2); // 그 군의 몇번째 위치에 있는지
}
int main () {
int n; // n번째 분수
int group, loc;
scanf("%d", &n);
loc = which_group(n, &group);
if (group % 2) { // 홀수인 경우
printf("%d/%d", group + 1 - loc, loc);
} else { // 짝수인 경우
printf("%d/%d", loc, group + 1 - loc);
}
return 0;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 3009번 C언어 풀이 (0) | 2021.09.10 |
---|---|
백준 2869번 C언어 풀이 (0) | 2021.09.09 |
백준 4948번 C언어 풀이 (0) | 2021.09.09 |
백준 2775번 C언어 풀이 (0) | 2021.08.30 |
백준 15829번 C언어 풀이 (0) | 2021.08.27 |