beaekjoon 1193

백준 1193번

백준 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번, …

n이 주어졌을때 n번째 분수를 구하는게 목표이다.

풀이

1) 위 배열을 다음과 같이 볼 수 있다

1/1					1개
1/2	2/1				2개
3/1	2/2	1/3			3개
1/4	2/3	3/2	4/1		4개
5/1	4/2	3/3	2/4	1/5	5개

행을 i이라고 하면 다음과 같다

i= 1 , 총 분수 1개

i= 2 , 총 분수 1 + 2 개

i= 3 , 총 분수 1 + 2 + 3개

i= 4 , 총 분수 1 + 2 + 3 + 4개

즉 N행에 있는 분수의 수는 i * (i+1)/2 개 이다.

이를 이용해 우리가 받은 수가 몇번째 라인에 있는지 확인 할 수 있다.

(1+2+3….+i-1)< num <= (1+2+3…i)

#include <stdio.h>

int main()
{
    int num, i = 1;
    scanf("%d", &num);

    while(1)
    {
        if( (i-1) * i / 2 < num && num <= (i) * (i+1) / 2 )
        {
            break;
        }
        i++;
    }
    return 0;
}

2) i번째 라인에 있는 분수의 숫자들의 합은 i+1이다.

ex)

i=2

[1/2 , 2/1] -> 총합 3

i=3

[3/1 , 2/2 , 1/3 ] -> 총합 4

3) i 가 짝수일때, 홀수일때

짝수이면 다음 숫자로 가면 갈수록 / 기준 왼쪽은 +, 오른쪽은-

홀수이면 다음 숫자로 가면 갈수록 / 기준 왼쪽은 -, 오른쪽은 +

 #include <stdio.h>

int main()
{
    int a = i(i+1) / 2;  //몇번째인지 비교를 위함 a-num 을 하면 라인에서 몇번째인지 알 수 있음

    if(i % 2 == 0) //  짝수이면
    {
        printf("%d/%d",(a-num) +1, i-(a-num));
    }
    else
    {
        printf("%d/%d",i- (a-num) , (a-num) +1 );
    }
    return 0;
}

결과 코드

 #include <stdio.h>

int main()
{
    int num, i = 1;
    scanf("%d", &num);

    while(1)
    {
        if( (i-1) * i / 2 < num && num <= (i) * (i+1) / 2 )
        {
            break;
        }
        i++;
    }
    int a = i(i+1) / 2;  

    if(i % 2 == 0) 
    {
        printf("%d/%d",(a-num) +1, i-(a-num));
    }
    else
    {
        printf("%d/%d",i- (a-num) , (a-num) +1 );
    }

    return 0;
}

이문제는 수학적 사고력을 많이 요구하는 문제여서 처음에는 조금 힘들었지만 재미있는 문제였다.