백준 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>
#include <string.h>
#define true 1
 
int main()
{
    //1 2 3 4 5 6 7  8 9 10 ...
    //1 3 6 10 15 21
    /*
    1-1
    2-1+2  ->
    3-1+2+3  <- 
    4-1+2+3+4  ->
    5-1+2+3+4+5  <-
    
    */
    int x;
    scanf("%d",&x);
    int line=1;
    while(true){
        if(((line-1)*(line))/2 < x && x<=((line)*(line+1))/2){
            break;
        }
        line++;
    }
    int temp = ((line)*(line+1))/2;
    if(line%2 == 0 ){
        
        printf("%d/%d",line-(temp-x),temp-x+1);
    }else{
        printf("%d/%d",temp-x+1,line-(temp-x));
        
    }
    return 0;
}

 

입력받은  x가 몇번째 대각선 라인에 위치해 있는지 아는게 우선이다.

라인 별로 1,2,3,4,5,6,7,8.... 로 하나씩 늘어나기 때문에

x가 위치하는 라인은 ((line-1)*(line))/2 < x && x<=((line)*(line+1))/2) 을 만족해야 한다.

line 을 찾았다면

line 이 짝수냐 홀수냐에 따라서 지그재그 방향이 달라진다

짝수 라인은 오른쪽 방향으로, 홀수 방향은 왼쪽 방향으로 진행하기 때문에

각 라인 최대값 기준으로 x의 위치를 결정하면 된다.