[백준 BOJ] 1933 분수찾기

1193_분수찾기

 

링크

https://www.acmicpc.net/problem/1193

 

풀이

 

규칙을 찾아보면 이렇게 된다는 것을 알 수 있습니다.

 

군수열처럼 이렇게 두고, 군(i)과 항(offset)을 찾아내서 풀면 됩니다.

홀수 군일 때는 i에서 offset을 뺀 것/offset + 1이고, 짝수 군일 때는 그 반대로 출력하면 됩니다.

offset은 n에서 min을 빼서 구할 수 있습니다.

 

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

//1193_분수찾기 #include <stdio.h>   int main() {     int n, min = 0, max = 0 , offset;     int i = 0;       scanf("%d", &n);       while (1) {                            //군 구하기         i++;         max = i * (i + 1) / 2;         min = max - (i - 1);         if (min <= n && max >= n)        //min : 1, 2, 4, 7 ...  max : 1, 3, 6, 10 ...             break;     }       offset = n - min;                    //항 구하기          if (i % 2 == 1)                        //군이 홀수         printf("%d/%d\n", i - offset, offset + 1);     else                                //군이 짝수         printf("%d/%d\n", offset + 1, i - offset);       return 0; } Colored by Color Scripter

cs