728x90
반응형
분수찾기
문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
| 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
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
27
28
29
30
31
32
33
34
35
36
|
#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;
}
|
cs |
입력받은 x가 몇번째 대각선 라인에 위치해 있는지 아는게 우선이다.
라인 별로 1,2,3,4,5,6,7,8.... 로 하나씩 늘어나기 때문에
x가 위치하는 라인은 ((line-1)*(line))/2 < x && x<=((line)*(line+1))/2) 을 만족해야 한다.
line 을 찾았다면
line 이 짝수냐 홀수냐에 따라서 지그재그 방향이 달라진다
짝수 라인은 오른쪽 방향으로, 홀수 방향은 왼쪽 방향으로 진행하기 때문에
각 라인 최대값 기준으로 x의 위치를 결정하면 된다.
반응형
'백준 단계별로 풀어보기 > 기본 수학 1' 카테고리의 다른 글
| 백준 10757 큰 수 A+B (0) | 2022.10.23 |
|---|---|
| 백준 2839 설탕 배달 (1) | 2022.10.07 |
| 백준 10250 ACM 호텔 (1) | 2022.10.05 |
| 백준 2775 부녀회장이 될테야 (1) | 2022.10.05 |
| 백준 2869 달팽이는 올라가고 싶다 (0) | 2022.09.20 |