백준 1193 분수찾기

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

문제해결

문제를 보고 짝수번째 행과 홀수번째 행에 대한 규칙은 금방 찾았으나 어떻게 입력으로 주어진 x번째에 위치한 값을 찾을지에 대한 방법은 찾기 어려웠다. 특히 몇 번째 칸에 위치했는지 파악하는 과정과 분자를 구하는 과정이 어려웠다. 힌트 참고해서 노트에 한참을 끄적이다가 두 시간만에 이해했다.

어떤 규칙이 있는지, 필요한 변수는 무엇인지에 중점을 두고 풀이했다.

먼저, 짝수번째 행에 위치한 분수의 경우 분자는 증가하고, 분모는 감소하는 반면, 홀수번째 행에 위치한 분수의 경우 분자는 감소하고, 분모는 증가하는 규칙을 찾았다.
두 번째로 몇 번째 행에 위치했는지 파악하기 위해 line 변수를 선언하였고 입력으로 주어진 x번째 위치한 값을 찾기 위해 sum 변수를 선언하였다. sum은 전체 데이터의 개수 즉, 누적 데이터의 개수를 저장하는 변수이다.
마지막으로 분자와 분모를 구하기 위해 변수 a와 b를 선언하였다. 분자 a의 경우 몇 번째 라인의 몇 번째 데이터인지를 의미하며 line - (sum - n)으로 정의하였다. 분자 b의 경우 line + 1 - a로 정의하였는데 a + b = line + 1이기 때문이다.

소스코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 전체 데이터 개수를 세기 위한 변수
        int sum = 0;
        // 몇 번째 행에 위치했는지 파악하기 위한 변수
        int line = 1;
        while (true) {
            sum += line;
            if (n <= sum) {
                int a = line - (sum - n); // 분자
                int b = line + 1 - a; // 분모
                // 짝수번째 라인은 분자 증가 / 분모 감소
                if (line % 2 == 0) {
                    System.out.printf("%d/%d", a, b);
                } else { // 홀수번째 라인은 분자 감소 / 분모 증가
                    System.out.printf("%d/%d", b, a);
                }
                break;
            }
            line++;
        }
    }
}