[C] <BAEKJOON> 백준 1193번 : 분수찾기

 

 

1193번 - 분수찾기

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초 (추가 시간 없음)	256 MB	35321	17184	15321	52.886%

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

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)가 주어진다.

출력

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

제한

 

예제 입력 1

14

예제 출력 1

2/4

힌트

 

 

풀이

패턴 찾기 - 1

 

행과 분자가 같이 증가하고

열과 분모가 같이 증가한다.

 

n행 1열과 1행 n열을 제외한 나머지

 

대각선으로 분자나 분모가 서로 반대로 증감한다.

 

 

 

 

패턴 찾기 - 2 

 

배열을 피라미드 형태로 기울 때

 

 

n 줄은 n개의 분수를 가진다.

 

 

 

또한 n이 짝수일 경우 분자에 n

n이 홀수일 경우 분모에 n을 가진 분수로 시작하는 순서를 가진다.

 

 

 

풀이 -1

 

 

구해야 하는 값은 크게 2가지

1. 입력값의 n줄

2. n줄의 i번 째 분수인지

 

 

 

1번

줄은 n으로 하고 n은 0부터 시작한다

sum에 n을 더하는 과정이다.

 

입력값의 분수가 n줄이라는 것을  확인하기 위해서

n+1줄이 아니라는 것을 확인하는 과정을 추가했다.

 

 

 

 

2번

i=input-sum

n줄에서 입력값의 분수의 순서는 i이다

 

그러나 반복문은 i-1 만큼 실행해야 하기 때문에

i=input-sum-1 

 

 

 

 

 

 

#include <stdio.h>
int main(){
        int n=0; //input의 분수가 존재하는 n
        int sum=0;
        int input;
 
        scanf("%d",&input);
 
        while(1){
                sum+=n;
                if(sum+n+1>=input) break;
                n++;
        }
 
        int i=input-sum-1; //반복문 조건
        int up;
        int down;
 
        if(n%2==0){
                up=1;
                down=n;
 
                for(int j=0; j<i; j++){
                        up++;
                        down--;
                }
        }
        else{
                up=n;
                down=1;
 
                for(int j=0; j<i; j++){
                        up--;
                        down++;
                }
        }
        printf("%d/%d\n",up,down);
 
        return 0;
}

#include <stdio.h>
int main(){
        int x;
        int i=1;
        scanf("%d", &x);
        while(1){
                if(x-i<=0) break;
                x-=i++;
        }
        int up;
        int down;
        if(i%2==0){
                up=1+(x-1);
                down=i-(x-1);
        }
        else{
                up=i-(x-1);
                down=1+(x-1);
        }
        printf("%d/%d",up,down);
        return 0;
}