백준 1193번 규칙찾기/분수찾기

문제: 규칙찾기/분수찾기

지그재그 순서로 배열된 분수들은 다음과 같은 순서로 배치된다.

1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1…

일렬로 배치해놓고 보면 다음과 같은 규칙성을 발견할 수 있다.

• 수열은 다음과 같은 그룹으로 분류할 수 있다. [1/1], [1/2. 2/1]. [3/1, 2/2, 1/3]…
• 각 그룹의 첫번째 분수에서 분자와 분모 중, 큰 값을 n이라고 하자. 이 때 1부터 n-1까지의 합에 1을 더한 값은, 그룹의 첫번째 분수가 몇 번째 값인지를 나타낸다. (단, 1은 제외한다.)
• 각 그룹의 첫번째 분수에서 분자와 분모 중, 큰 값을 n이라고 하자. 이 때 n이 짝수인 경우에는 n이 분모가 되며, n이 홀수일 경우에는 n이 분자가 된다.

따라서 필요한 것은 다음과 같다.

• 입력값 k가 주어졌을 때 sum(1~n-1)을 만족하는 값 중, 결과값이 k보다 작은 최대값이 필요하다. 이 값은 그룹의 시작값이 된다.
• 위에서 구한 n값이 짝수인지 홀수인지 판별이 필요하다.

sum(1~n-1)은 n(n-1)/2로 계산할 수 있다. 또한 n값이 짝수인지는 모듈러 연산을 이용해서 구할 수 있다.

최종적으로 작성한 코드는 다음과 같다.

#include <stdio.h>

int main() {
    int input_data=0, n=1;
    int is_even=0;
    int start_value=0;

    int bigger=0, smaller=0;

    scanf("%d", &input_data); //입력값을 받는다.

    if(input_data==1) { //1일 경우에는 연산을 하지 않고, 1/1을 출력한 뒤 종료한다.
        printf("1/1");
        return 0;
    }

    //n(n-1)/2보다 input_data의 값이 커질때까지 n을 증가시킨다. 이를 통해 n+1값을 구할 수 있다.
    while(input_data > (n*(n-1))/2) {
        n++;
    }
    n-=1; //n을 구한다.

    //위에서 구한 n값이 짝수인지 판별한다.
    if(n%2==0) {is_even = 1;}
    else {is_even = 0;}

    start_value = ((n*(n-1))/2)+1; //그룹의 시작값이 몇번째 분수인지 구한다.

    bigger = (n)-(input_data-start_value); //위에서 구한 n값에서, 입력값과 시작값의 차를 빼준 값이 큰 값이 된다.
    smaller = (1)+(input_data-start_value);//1에서 입력값과 시작값의 차를 더해준 값이 작은 값이 된다.

    if(is_even==1){
        printf("%d/%d", smaller, bigger); //짝수일 경우 큰 값이 분모가 된다.
    } else {
        printf("%d/%d", bigger, smaller); //홀수일 경우 작은 값이 분모가 된다.
    }

    return 0;
}

​