Baekjoon1193: 분수찾기

Baekjoon1193: 분수찾기

문제

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

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

출력

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

추상화

2292벌집문제와 동일하지만 순서를 구해야한다.

1) num은 0에서부터 출발한다

2) num은 움직일 때마다 한 칸이 아니라 한 라인의 끝점으로 이동한다

→ 1, 3(1+2), 6(1+2+3), 10(1+2+3+4)...

3) 끝점으로 이동할 때마다 room이 한 개씩 증가한다

4) num이 사용자가 입력해준 값 N보다 커지면 멈춘다

5) N과 num의 차이를 계산해 얼마나 뒤로 움직여야 하는지 구해준다

6) room과 계산한 차이를 이용해 값을 구해준다

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int num = 0; int room =0; for( int i =1; num < N; i++) { num += i; room ++; } //벌집과 형식은 같다 int diff = num-N; //하지만 차이를 계산해서(diff) 몇번째인지 계산한다 if(room%2 ==0) { System.out.print(room-diff+"/"+(diff+1)); } else { System.out.print(diff+1+"/"+(room-diff)); } //room이 짝수인 경우 위에서 아래, 홀수인 경우 아래에서 위로 num이 이동한다 } }

from http://devyoseph.tistory.com/52 by ccl(A) rewrite - 2021-10-12 03:28:00