[백준] 1193 - 분수 찾기

1. 문제

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번째 분수를 구하는 프로그램을 작성하시오.

2. 내 풀이

대각선 경로 하나당 한 사이클의 규칙을 찾아 코드를 작성했다

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

import java.util.Objects;


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

        int input = Integer.parseInt(bf.readLine());
        int count = 1; // 현재 수
        int check = 1; // 기준 수

        while(true){
            if(input==1){
                bw.write("1/1");
                break;
            }
            if(count+check<input){
                count=count+check; // 현재 수
                check++; // 기준 수 증가
            }
            else if(count+check>input){
                bw.flush();
                int k =(input-count)+1;
                int n =(count+check)-input;
                if(check%2==1){
                    //기준 수가 홀수일 경우
                    bw.write(n+"/"+k);
                    bw.flush();
                    break;
                }
                else{
                    // 기준 수가 짝수일 경우
                    bw.write(k+"/"+n);
                    bw.flush();
                    break;
                }
            }
        }



        bw.close();

    }

}

위 풀이는 시간초과가 걸렸다.

생각해보니까 count+check == input 인 경우를 if문에 넣어주지 않았다.
(위 이유때문에 특정 수에서 무한루프 돌았음)

하지만 위 조건을 넣어줄 경우 input이 2일때 바로 결과를 출력하는 if문으로 넘어가게 된다.

바로 넘어갈 경우 기준 수가 1인데 두번째 라인에서 함수가 돌고있는 엉뚱한 상황이 발생한다.

처음에 시간초과가 떳길래 풀이를 찾아봤는데 나랑 똑같은 로직이라 일부분을 수정하여 리팩토링 하였다.(변수명 변경 등등)

3. 최종 풀이

import java.io.*;


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

        int input = Integer.parseInt(bf.readLine());
        int prevLastnum = 0; // 이전 라인의 마지막 수
        int cross_count = 1; // 이번 라인에서의 분수의 나열 갯수

        while(true){
            if(input==1){
                bw.write("1/1");
                break;
            }
            if(prevLastnum + cross_count <input){
                prevLastnum = prevLastnum + cross_count; // 이전 라인의 마지막 수 증가(범위 내에 없으므로 끝까지 보냄)
                cross_count++; // 다음라인(분수 나열갯수 증가)
            }
            else if(prevLastnum + cross_count >=input){
                bw.flush();
                int k =(input- prevLastnum);
                int n =(prevLastnum + cross_count)-input+1;
                if(cross_count %2==1){
                    //라인 수가 홀수일 경우
                    bw.write(n+"/"+k);
                    bw.flush();
                    break;
                }
                else{
                    // 라인 수가 짝수일 경우
                    bw.write(k+"/"+n);
                    bw.flush();
                    break;
                }
            }
        }



        bw.close();

    }

}