[C/C++] 백준 1193번 C언어

백준 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번, 2번, 3번, 4번, 5번, … 분수라고 하자.

 

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

 

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

첫째 줄에 분수를 출력한다.

 

#include <stdio.h>

int main()
{
        int W=1,H=1, Prev,Next, result=0;
        int input;
        scanf("%d", &input); // 최대 입력될 수 있는 숫자 1천만

        // 정사각형으로 자름 1/1, 2/2, 3/3, 4/4, ....
        // 끝점이니 넓이로 계산하고 값만 중첩
        // 기준점은 항상 대각선 방향으로 나열된 값 중 중간값을 가짐

        while(1){
                // 기준점 설정
                if(result>=input){ break; }
                Prev = W*H;
                W++; H++;
                Next = W*H;
                result = Next+Prev;
        }

        // 예외 처리
        if(result!=input){
                Prev= result-input;
                if(Prev < H){
                        // 좌측 하단 대각선 방향
                        H= H+Prev;
                        W= W-Prev;
                }else{
                        // 기준점 변경 (한칸 위)
                        H-=1;
                        // Prev = result - (H*2+1); result가 항상 중간값이므로 계산 가능
                        Prev = H*H*2;
                        if(Prev==input) {
                                printf("%d/%d", H, W);
                                return 0;
                        }
                        if(Prev<input){
                                // 입력값이 기준점보다 더 크면 (좌측 하단 대각선 방향)
                                result = input-Prev;
                                H=H+result;
                                W=W-result;
                        }
                        if(Prev>input){
                                // 입력값이 기준점보다 더 작으면 (우측 상단 대각선 방향)
                                result = Prev-input;
                                H=H-result;
                                W=W+result;
                                if(H==0){
                                        // 0은 유효 숫자 범위가 아니기 때문에 따로 처리
                                        H+=1;
                                        W-=2;
                                }else if(H<0){
                                        // 부호 반전 연산
                                        H = ~H+2;
                                        W = W-H*2;
                                }
                        }
                }
        }
        printf("%d/%d", H,W);
        return 0;
}

 

문제에 나와있는 분수를 보고 힌트를 얻었는데, 누가 봐도 Height / Width를 표현한 것 같아서 일단 사각형으로 잘라내고 넓이 값을 중첩해가며 다음 기준점을 계산했다.

 

1/1 -> 1 : 1*1

2/2 -> 5 : 2*2 + 1*1

3/3 -> 13 : 3*3 + 2*2

....

 

시간제한이 있는 문제라 걱정했는데 십진수의 연산 속도가 가장 빠르기 때문에 시간제한에 걸리진 않았다.

또한 입력값과 직접적인 비교/연산이 가능하여 코드를 더 쉽게 짤 수 있었다.

 

위 코드에선 입력받은 값이 포함될 때까지 넓이를 더해가며 정사각형 모양을 만든다(있다고 가정).

 

이때 입력값의 범위는 result보다 항상 작으며 이전 기준점보단 항상 크다.

일정 범위 내에서 값을 구하면 되기 때문에 예외 처리만 꼼꼼하게 해주면 쉽게 답을 구할 수 있다.