[백준 / BOJ] 1193번 : 분수찾기 (Java)

문제

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

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

 

출력

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

 

전체 코드(Java)

import java.io.*;

public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int A = 1;
        int B = 1;
        boolean flag = true;
        int X = Integer.parseInt(br.readLine());
        int count = 1;

        while (count != X) {
            if (flag == true) {
                if (A == 1) {
                    B++;
                    flag = false;
                    count++;
                }
                else {
                    A++;
                    flag = false;
                    count++;
                }
            }
            else {
                if (A == 1) {
                    for (; B != 1 && count != X; A++, B--) {
                        count++;
                    }
                    flag = true;
                }
                else {
                    for (; A != 1 && count != X; A--, B++) {
                        count++;
                    }
                    flag = true;
                }
            }
        }

        bw.write(String.valueOf(A + "/" + B));

        bw.flush();
        bw.close();
        br.close();
    }
}

 

풀이

1. X가 1일 때 "1/1"이 출력되므로, A,B의 초기값을 1/1로 설정
2. 이동 패턴 분석
   • 좌표가 지그 재그 형태로 움직임
   • A/B로 나타냈을 때 A 또는 B가 변화할 때 마다 1번 움직인 것으로 측정
   • (a) 대각선으로 이동 => (b) A가 1일 때 B+1 / (c) B가 1일 때 A+1 => (a)대각선으로 이동의 패턴 반복
     • 초기 값인 1/1일 때는 패턴 (b)인 B+1로 시작
   • flag라는 boolean 변수를 이용해서 "(a)" 또는 "(b), (c)로 움직여야 하는 경우"를 결정
     • flag가 true일 때는 (b) 또는 (c)로 움직여야 하는 상황, (b)와 (c)는 A, B 중 어떤 것이 1인가에 따라 결정
     • flag가 false일 때는 (a)로 움직여야 할 상황, 대각선으로 이동하며 A/B 중 어떤 것이 1인가에 따라 방향 결정
       • A가 1이라면 A는 1씩 더하고, B는 1씩 빼서 B가 1이 되거나 count가 목표한 횟수가 될 때 까지 반복소감

• 생각할 시간이 필요한 문제였음
• 소요 시간이 204ms로 상위권 제출자의 시간인 128~140ms에 비하면 느리다고 할 수 있음
  • 최적화 할 수 있는 방법이 존재
• 본 코드는 if else 문을 이용해 모든 이동 패턴을 (그나마) 직관적으로 알 수 있다는 점에서 장점이 있다고 생각
  • 모든 행동 패턴은 크게 4가지로 분류됨. (a) 패턴은 A가 증가하고 B가 감소하는 (a-1) 패턴과 B가 증가하고 A가 감소하는 (a-2) 패턴으로 나눌 수 있으며 총 (a-1), (a-2), (b), (c)로 모든 패턴이 나눠진다고 할 수 있음