[백준] 1193번 - 분수찾기 (Java)

문제 

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

1193번: 분수찾기

 

코드

import java.util.Scanner;

// 분수찾기
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 1;          // i번째

        for (int i = 1; ; i++) {
            int j = 1;
            if (i % 2 == 0) {   // 짝수번째 차례에는 위에서부터 시작
                for (j = 1; j <= i; j++) {
                    if (count == n) {
                        System.out.println(j + "/" + (i - j + 1));
                        break;
                    }
                    count++;
                }
            } else {            // 홀수번째 차례에는 아래에서 부터 시작
                for (j = 1; j <= i; j++) {
                    if (count == n) {
                        System.out.println((i - j + 1) + "/" + j);
                        break;
                    }
                    count++;
                }
            }
            // for문이 끝까지 진행되지 못 하고 break 조건에 걸렸을 경우
            if (j != i + 1) {
                break;
            }
        }
    }
}

 

분수찾기에서 순번을 매기는 순서에 주의하자. 지그재그 방향으로 나아가기 때문에 1/1, 1/2, 2/1, 3/1, 2/2, 1/3... 과 같이 두번째 그림처럼 대각선 라인별로 구분했을 때, 각 라인 별로 진행방향이 달라진다. 한번씩 차례대로 진행 방향이 바뀌기 때문에 짝수 번째 라인에서는 위→아래 방향으로, 홀수 번째 라인에서 아래→위 방향으로 순번을 매긴다고 생각하면 된다.

(1) / (2) / (3)

위에서 2번째 그림과 같이 각 라인 안에서 일정한 규칙에 따라 분수들이 정해진다. 라인 안에 포함된 분수를 i/j 형태로 볼 때 i가 +1씩증가하고, j가 -1씩 감소하는 규칙적인 형태를 취한다.
ex) 2번째 라인 = { 2/1, 1/2 }, 4번째 라인 = {4/1, 3/2, 2/3, 1/4} 

이는 이중 for문으로 구현할 수 있다. 바깥쪽 for문 (i번째 라인) + 안쪽 for문 (j번째 분수)

다만, 처음에 설명한 것과 같이 짝수 번째 라인일 때 / 홀수 번째 라인일 때 j의 진행 방향이 다름에 유의하자.
번호를 매기는 순서는 { 1/1 → 1/2, 2/2 → 1/3, 2/2, 3/1 } 이 아니라 { 1/1 → 1/2, 2/2 → 3/1, 2/2, 1/3 } 이다.

이렇게 차례대로 1부터 무한반복으로 순번을 구해나다 입력받은 n번째 순번인 경우(count==n) 해당 순번에서의 분수 값을 String 형태로 형식화해서 출력한 뒤, 이중 for문을 탈출하면 된다.

 

다른 사람의 코드

다른 사람의 코드를 참고하여 개선한 코드.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int currCount = 1;      // 현재 대각선 칸 개수
        int prevCountSum = 0;   // 이전 대각선 칸 개수 누적 합

        while (true) {
            // 현재 대각선의 마지막 순번보다 작거나 같음
            if (n <= prevCountSum + currCount) {

                if (currCount % 2 == 0) {   // 대각선 개수가 짝수면 위 → 아래
                    System.out.println((n - prevCountSum) + "/" + (currCount - (n - prevCountSum - 1)));
                } else {                    // 대각선 개수가 홀수면 아래 → 위
                    System.out.println((currCount - (n - prevCountSum - 1)) + "/" + (n - prevCountSum));
                }
                break;

            } else {
                prevCountSum += currCount;
                currCount++;        // 대각선 칸 개수는 1칸씩 늘어남 (1, 2, 3, ...)
            }
        }
    }
}

각 대각선의 칸 개수로 n번째 분수가 존재하는 대각선까지 단순에 이동한 뒤 순서를 계산하기 때문에 내가 사용했던 방식에 비해 훨 빠르다. (미리 범위를 줄여두는, 소거법 방식) 단일 반복문이기 때문에 break; 방식도 이중 반복문에 비해 간단하다.

• 분자와 분수의 합이 같은 것끼리 같은 대각선 라인에 위치한다.
• 각 대각선의 칸(분수) 개수 = (분자 + 분수) - 1 개
• 대각선의 칸 개수와 분모+분자의 합 관계를 이용해 해당 대각선에서의 시작 분모, 시작 분자를 알아낼 수 있다.