자바 백준 1193 - 분수찾기 (설명 포함)

내 풀이

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

//분수찾기(1193)
public class Q_1193 {

    public static void main(String[] args) throws Exception  {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());
        int line = 0;
        int line_seq = 0;
        int cnt = 0;
        while(cnt<X) {
            line++;
            line_seq = 0;
            for(int i=0; i<line; i++) {
                cnt++;
                line_seq++;
                if(cnt==X) {
                    break;
                }
            }
        }
        int first = 0;
        int last = 0;
        for(int i=1; i<=line_seq; i++) {
            if(line%2==0) {
                first = i;
                last = line+1-i;
            } else {
                first = line+1-i;
                last = i;
            }
        }
        System.out.println(first + "/" + last);
    }
}

---

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

이와 같이 나열된 분수들을 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 → 2/1 → 3/1 → 2/2 → …

이 순서를 조금 보기 좋게 나열해보면

1/1
1/2 | 2/1
3/1 | 2/2 |	1/3
1/4 | 2/3 |	3/2 | 4/1
5/1 | 4/2 |	3/3 | 2/4 | 1/5
1/6 | 2/5 |	3/4 | 4/3 | 5/2 | 6/1
...

아래와 같은 규칙을 찾을 수 있다. 

홀수 라인은 앞자리가 라인 숫자부터 짝수 라인은 1부터 시작한다.

---

X번째가 몇 번째 라인의 몇 번째에 위치하는지 구해보자.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine()); //X번째 입력			ex) X가 5일 떄 2/2
        int line = 0;		//line 변수 									line = 3번째 라인의
        int line_seq = 0;	//해당 line의 몇번째 순번인지의 대한 변수		line_seq = 2번째 위치
        int cnt = 0;		//cnt 변수
        
        while(cnt<X) {					//cnt가 X보다 작을때까지만 반복
            line++;						//line + 1 (1, 2, 3, 4, 5 ...)
            line_seq = 0;				//line이 바뀌면(+1되면) 해당 라인의 순번은 초기화
            for(int i=0; i<line; i++) {	//line번 반복
                cnt++;					//cnt가 X가 될 때까지 증가
                line_seq++;				//cnt가 늘수록 순번도 증가
                if(cnt==X) {			//cnt==X일 때,
                    break;				//break;
                }
            }
        }
        //체크용 출력
        //System.out.println("line" + line + "의 " + line_seq + "번째에 위치합니다");

출력 결과

---

이제 라인과 해당 라인의 몇번째에 위치하는지 구했으니 출력을 구해보자.

홀수 라인은 앞자리가 라인 숫자부터 짝수 라인은 1부터 시작한다.

        //출력은 분수 형태이므로 first/last식으로 출력할 예정
        int first = 0;
        int last = 0;
        for(int i=0; i<line_seq; i++) {	//
            if(line%2==0) {		//짝수 line일 때
                first = i+1;		//frist가 1부터 오름차순
                last = line-i;		//last는 line부터 내림차순
            } else {			//홀수 line일 때
                first = line-i;		//first가 line부터 내림차수
                last = i+1;			//last는 1부터 오름차순
            }
        }
        System.out.println(first + "/" + last); //출력

출력 결과

---

더 좋은 풀이가 있겠지만 나는 위와 같은 방식으로 풀어냈다. 처음엔 한 4시간 고민하다가 안 풀려서 다른 문제부터 풀고 대략 일주일 만에 다시 풀어본 거 같은데 1시간정도 고민하고 풀어낸듯...? 진짜 풀어냈을 때 좀 많이 기쁨...!! 이 풀이를 보는 사람이라면 아마 조금 어려워서 찾아본 것 일텐데 도움이 되었으면 좋겠다...!!