[백준/C언어] 1193번 - 분수찾기

백준 웹사이트 "1193번 - 분수찾기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1193번: 분수찾기

---

소스 코드

#include <stdio.h>

int main(void){
    /*
        X = 1 : 1/1
        X = 2 ~ 3 : 1/2 ~ 2/1
        X = 4 ~ 6 : 3/1 ~ 1/3
        X = 7 ~ 10 : 1/4 ~ 4/1
        ...
        X = 1+2+...+(n-1)+1 ~ 1+2+...+n : 1/n ~ n/1 (n: 짝수)
        X = 1+2+...+(n-1)+1 ~ 1+2+...+n : n/1 ~ 1/n (n: 홀수)
    */
    int X;
    scanf("%d", &X);

    int n=1;
    while(1){
        // X = 1+2+...+(n-1)+1 ~ 1+2+...+n -> X = (n-1)*n/2 + 1 ~ n*(n+1)/2
        if((n-1)*n/2+1<=X && X<=n*(n+1)/2){ // X의 범위 찾기
            break;
        }
        n++;
    }

    int numerator, denominator;
    if(n%2==0){ //n이 짝수
        numerator = X-(n-1)*n/2; //분자
        denominator = (n+1) - numerator; //분모
    }
    else{   //n이 홀수
        denominator = X-(n-1)*n/2; //분모
        numerator = (n+1) - denominator; //분자
    }
    printf("%d/%d", numerator, denominator);
}

---

문제 풀이

  규칙만 찾으면 코드 작성은 크게 어렵지 않은 문제입니다. 지그재그로 분수들을 적기 때문에, 짝수번째 대각선과 홀수번째 대각선은 분수들이 반대로 쓰입니다. 이를 고려하여 분수들을 보면, 아래와 같은 규칙을 찾을 수 있습니다.

X = 1 : 1/1
X = 2 ~ 3 : 1/2 ~ 2/1
X = 4 ~ 6 : 3/1 ~ 1/3
X = 7 ~ 10 : 1/4 ~ 4/1

---

X = 1+2+...+(n-1)+1 ~ 1+2+...+n : 1/n ~ n/1 (n: 짝수)
X = 1+2+...+(n-1)+1 ~ 1+2+...+n : n/1 ~ 1/n (n: 홀수)

1/1부터 첫 번째 대각선이라고 생각했을 때, n번째 대각선에는 1/n 부터 n/1까지의 분수들이 적힙니다. 이때 한 가지 더 발견할 수 있는 것이, 같은 대각선 상에 놓인 숫자들은 분자와 분모의 합이 같다는 점입니다. 따라서 n번째 대각선에 적히는 분수들은, 분자와 분모의 합이 n+1입니다.

  지금까지 알아낸 규칙을 바탕으로 코드를 작성합니다. Line 17 ~ 23의 while문은 X의 범위를 찾는 반복문입니다. X가 몇 번째 대각선에 존재하는지 알아내기 위해, n을 1부터 증가시키며 확인합니다. X가 n번째 대각선에 속한다면, n을 증가시키지 않고 반복문을 빠져나옵니다. Line 25 ~ 33에서는 분자(numerator)와 분모(denominator)를 구합니다. 위에 구한 규칙 중, 짝수번째 대각선과 홀수번째 대각선은 반대라는 규칙이 었죠? 두 가지 경우를 나누어, 분자와 분모를 각각 구하면 됩니다.