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

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

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

 

문제 접근

대각선 1	1/1
대각선 2	1/2	2/1
대각선 3	3/1	2/2	1/3
대각선 4	1/4	2/3	3/2	4/1
대각선 5	5/1	4/2	3/3	2/4	1/5

• 분자와 분모의 합 = 대각선 번호 + 1
• 각 대각선의 칸의 수 = 대각선 번호
• 대각선 번호가 짝수이면 분자는 증가, 분모는 감소
• 대각선 번호가 홀수이면 분자는 감소, 분모는 증가

대각선의 수 : diagonal

현재 대각선 이전까지의 칸의 개수 : count

분모 : deno

분자 : num

• 입력값이 어떤 대각선에 해당하는 지 계산하고
• 해당하는 대각선이 홀수인지 짝수인지 판별하여 분모, 분자 값을 구함

 

풀이1 - Scanner 사용

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //Scanner 사용
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();

        System.out.println(new Solution().solution(n));

    }
}

class Solution{
    public String solution(int n){
        int diagonal = 1; // 대각선의 수
        int count = 0;  // 전체 칸의 수

        int num = 0;    // 분자
        int deno = 0;   // 분모

        while(true){
            if(n <= diagonal + count){
                if(diagonal % 2 == 0){  // 대각선 번호가 짝수
                    num = n - count;
                    deno = diagonal - (n-count-1);
                    break;
                } else{             // 대각선 번호가 홀수
                    num = diagonal - (n-count-1);;
                    deno = n - count;
                    break;
                }
            }else{
                count += diagonal;
                diagonal++;
            }
        }
        return (num  + "/" + deno);
    }
}

 

풀이2 - BufferReader 사용 (알고리즘은 동일하다)

• 입력된 데이터가 바로 전달되지 않고 버퍼를 거쳐 전달되므로 데이터 처리 효율성을 높임
• 시간 절약 가능, 많은 양의 데이터를 처리할 때 유리

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

public class Main {
    public static void main(String[] args) throws IOException { // 예외처리 필요
        // BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // int로 변환하는 과정 필요

        System.out.println(new Solution().solution(n));

    }
}

시간비교

	메모리	시간
Scanner	18476 KB	232 ms
BufferReader	16088 KB	152 ms