📔문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
| 1 | 2 | 3 | 4 | 5 | ... |
|---|---|---|---|---|---|
| 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
1📺예제 출력 1
1/1📝예제 입력 2
2📺예제 출력 2
1/2📝예제 입력 3
3📺예제 출력 3
2/1📝예제 입력 4
4📺예제 출력 4
3/1📝예제 입력 5
5📺예제 출력 5
2/2📝예제 입력 6
6📺예제 출력 6
1/3📝예제 입력 7
7📺예제 출력 7
1/4📝예제 입력 8
8📺예제 출력 8
2/3📝예제 입력 9
9📺예제 출력 9
3/2📝예제 입력 10
14📺예제 출력 10
2/4🔍출처
-문제를 만든 사람: author6
-문제의 오타를 찾은 사람: deadlylaid
-어색한 표현을 찾은 사람: djm03178
-데이터를 추가한 사람: mj2park
🧮알고리즘 분류
- 수학
- 구현
📃소스 코드
import java.util.Scanner;
public class Code1193 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
boolean isRoop=true;
int i=1;
int sum=0;
int temp=0;
int up=0;
int down=0;
while(isRoop) {
sum=i*(i+1)/2; //sum(1..i)
if(sum>=n) {
isRoop=false;
break;
}
i++;
}
if(i%2==0) { //even
temp=sum-((i-1)*i/2);
n=n-((i-1)*i/2);
up=1;
down=temp;
for(int j=1;j<n;j++) {
up++;
down--;
}
System.out.println(up+"/"+down);
}else {
if(i==1) {
System.out.println("1/1");
}
else {
temp=sum-((i-1)*i/2);
n=n-((i-1)*i/2);
up=temp;
down=1;
for(int j=1;j<n;j++) {
up--;
down++;
}
System.out.println(up+"/"+down);
}
}
}
}
📰출력 결과
📂고찰
사실 전혀 감을 못잡고있었는데,
(직접 그렸다..)
이런 힌트를 발견했다.
홀수라면 분자는 감소하고, 분모는 증가
짝수라면 분자는 증가하고, 분모는 감소여기에, 어제 1~10까지 구하는 공식(n(n+1)/2)을 아냐고 물으며 그거를 잘 사용해보라던 우리 언니.. 덕분에 해결할 수 있었다.
일단 입력받은 수가 짝수층인지 홀수층인지 알아야 했다.
그것을 위해서 i를 도입하였고, 1부터 i까지의 합이 입력값보다 크거나 같아지면, while문에서 탈출하였다.
그렇다면 그 i까지의 합안에 입력값이 있는 것 아닌가!
그래서, 이제 구한 i층이 홀수인지 짝수인지 구분했다.
그리고, temp=sum-((i-1)*i/2)는 해당 층의 애들 수를 구하기 위해 도입했다.
n=n-((i-1)*i/2);는 현재 구하려고 하는 n이 그 층에서 어느 위치에 있는지를 구하기 위함이었다.
이를 토대로, 1부터 (ex.14-(4층까지의 합인)10=4이고, 시작은 1부터이므로) n(n은 그 층에서의 위치값으로 변경되었다)까지 for문을 돌리며 계산하였다.
뿌듯..
