본문 바로가기

컴퓨터/백준 알고리즘

백준 알고리즘 1193번: 분수찾기 C언어

문제 출처: www.acmicpc.net/problem/1193

 

1193번: 분수찾기

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

www.acmicpc.net

1. 코드

#include <stdio.h>

int main(void)
{
    int x, key = 0, i = 2, j = 1, k, cnt = 2;
    
    scanf("%d", &x);
    
    if(x == 1)
    {
        printf("1/1");
        return 0;
    }
    
    while(1)
    {
        if(i <= x && i + j >= x)
        {
            if(j % 2 == 1) key = 0;
            else key = 1;
            break;
        }
        i = i + j + 1;
        j++;
    }
    
    i = 2;
    while(1)
    {
        j = 1;
        for(k = i; k > 0; k--)
        {
            if(x == cnt)
            {
                printf("%d/%d", (key == 1) ? k : j, (key == 1) ? j : k);
                return 0;
            }
            j++; cnt++;
        }
        i++;
    }
    return 0;
}

2. 문제 해결 방식

우선 문제를 이해하는 게 우선인 것 같다. 실제로 저는 문제를 잘못 이해해서 문제와 전혀 다른 방향으로 나아갔다. 그래서 문제를 이해하는 게 우선인데 알고 보면 문제는 간단하다.

파란색 줄을 따라 순서대로 나아가는 것이다. 그리고 해당하는 X의 순번에 맞는 분수를 찾으면 된다.

여기서 나는 저 그림을 이런 식으로 분류했다.

식별 값 0은 빨간 화살표를 1은 파란색 화살표를 의미한다. 분수를 임의로 a/b라고 가정하자. 그리고 그림을 보면 빨간 화살표 같은 경우에는 1/2 -> 2/1인데 a의 값이 점점 커지고, b의 값이 점점 낮아지고 있고, 파란 화살표 같은 경우에는 3/1 -> 2/2인데 a의 값이 점점 낮아지고, b의 값이 점점 커지고 있다.

식별 같을 통해서 이 방향을 식별하여 x에 해당하는 분수를 출력하면 된다.

x의 값이 1 같은 경우에는 분류하기가 애매하다고 판단해서 과감하게 제외시켜서 따로 출력하게 했다.

 

3. 느낀 점 

이 문제를 풀면서 문제를 이해하는 것이 상당히 중요하다고 느껴졌다. 나는 보통 문제를 보면 빠르게 입출력부터 보거나 나 입출력을 통해서 규칙을 찾으려고 한다. 사실 모든 규칙은 문제에 나와 있다는데도 말이다.

이번 기회를 통해서 문제를 조금 더 신중히 읽어보면서 풀어봐야겠다.