백준 1193번 C언어 풀이

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

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;
}