[백준] 1193번: 분수찾기 [JAVA]

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

문제

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

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/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	…	…	…	…	…
…	…	…	…	…	…

주어진 숫자를 x,

x가 존재하는 대각선이 몇 번째인지를 line이라고 하면,

 

line이 짝수일 때, 분모가 커지고 분자가 작아집니다.(방향이 왼쪽 아래로 진행)

line이 홀수일 때, 분자가 커지고 분모가 작아집니다.(방향이 오른쪽 위로 진행)

 

대각선이 1씩 증가할 때마다 대각선에 존재하는 분수의 개수가 1개씩 증가합니다. (등차수열)

따라서, x가 존재하는 대각선까지의 총 합(count)은 line * (line + 1) / 2 가 됩니다.

 

count에서 x를 빼면,

line이 짝수일 경우, count - x = 분모 - 1

line이 홀수일 경우, count - x = 분자 - 1 이 됩니다.

따라서, count - x + 1 이 홀짝에 따라 분모 또는 분자가 됩니다.

 

또한,

line에 1을 더한 값이 분모, 분자의 합이 됩니다.

count - x + 1이 분모라면 분자는 분수의 분모, 분자의 합에서 분모를 뺀 값,

count - x + 1이 분자라면 분모는 분수의 분모, 분자의 합에서 분자를 뺀 값이 됩니다.

 

이를 이용하여 코드를 작성하겠습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int x = Integer.parseInt(br.readLine());
    int line = 0;
    int count = 0;
    while(count < x) {
      line++; // line번째 대각선
      count = line*(line+1)/2; // x가 존재하는 대각선까지의 개수 총 합
    }
    if(line % 2 == 1) {
      int top = count - x + 1;
      int bottom = (line+1) - top; //분모 분자 합에서 분모 빼면 분자임.
      sb.append(top).append("/").append(bottom);
    }else {
      int bottom = count - x + 1;
      int top = (line+1) - bottom; //분모 분자 합에서 분자 빼면 분모임.
      sb.append(top).append("/").append(bottom);
    }
    System.out.println(sb);
  }
}

---

아직 이런 문제도 보고서 감이라도 바로 오지 않는 것을 보니 알고리즘 공부는 멀고도 멀었다는 생각이 듭니다.

이 글의 알고리즘이나 코드에서 지적할만한 부분은 댓글에 남겨주시면 저에게 많은 힘이 됩니다!