[백준] 1193번(Java)

📖 분수 찾기

[ 문제 ]

1/1	1/2	1/3	1/4	...
2/1	2/2	2/3	2/4	...
2/1	2/2	2/3	2/4	...
...	...	...	...	...

나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

💡풀이

• 나열된 분수들을 오른쪽 위에서 왼쪽 아래로 가는 대각선들끼리 묶어서 생각했다. n번째 대각선들의 원소들은 분자와 분모의 합이 n + 1이 된다는 점을 이용해 풀었다.
• ex) 3번째 대각선의 원소들 : 2/1, 2/2, 1/3 -> 각 원소들 모두 분자, 분모의 합이 3에 1만큼 추가한 4이다.
• 각 대각선들의 개수는 1, 2, 3... 로 1개씩 늘어나기 때문에 입력받은 수에서 1, 2, 3.. 씩 빼보면서 찾고자 하는 수가 몇 번째 대각선의 몇 번째 위치에 존재하는지를 확인한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        //분수 찾기 : 1193번
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int tmp = T ;
        int ans = 1;
        while(tmp > 0){
            tmp -= ans;
            ans += 1;
        }
        if ((ans - 1) % 2 == 0) {
            System.out.println( (tmp + ans - 1) + "/" + (1 - tmp));
        } else {
            System.out.println( (1 - tmp) + "/" + (tmp + ans - 1));
        }
    }
}

백준 1193번 : https://www.acmicpc.net/submit/1193/87949824