[BaekJoon] 1193번 분수찾기 문제풀이 (Success)

1193번: 분수찾기

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int n = Integer.parseInt(br.readLine());
        
        int sum = 0;
        int count = 0;
        for(int i=1;;i++) {
            sum += i;
            count ++;
            if(sum>n) {
                break;
            }
        }
 
        List<String> fractionList = new ArrayList<>();
 
        for (int i = 2; i <= count; i++) {
            for (int j = 1; (i-j) >0; j++) {
                fractionList.add(j + "/" + (i-j));
            }
        }            
 
        bw.write(fractionList.get(n-1) + "");
 
        bw.flush();
        bw.close();
 
    }
 
}
 

🚨 fractionList를 만들기 위해 count전까지의 모든 분수를 생성하므로 메모리 초과 발생

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        int cnt = 0;
 
        int i = 1;
        int j = 1;
        Loop: for (i = 1;; i++) {
            for (j = 1; j <= i; j++) {
                cnt++;
                if (cnt == N) {
                    break Loop;
                }
            }
        }
 
        if (i % 2 == 0) {
            bw.write(j + "/" + (i + 1 - j));
        } else {
            bw.write((i + 1 - j) + "/" + j);
        }
 
        bw.flush();
        bw.close();
 
    }
 
}
 

규칙을 찾아서 분수를 반환

대각선 n번째 줄	분자 + 분모	순번
1	2	1
2	3	2 3
3	4	4 5 6
4	5	7 8 9 10
5	6	11 12 13 14 15
6	7	16 17 18 19 20 21

1. 대각선의 몇번째 줄에 있는지 확인

예시1: 10번 → 4번째 줄에 위치

예시2: 5번 → 3번째 줄에 위치

2. 대각선에서 몇 번째 순서인지 확인

예시1: 10번 → 4번째 줄의 4번째 순서에 위치

예시2: 5번 → 3번째 줄의 2번째 순서에 위치

3. 경우의 수에 따라 분수 출력

대각선 줄이 짝수일 경우, 순번이 커질수록 분자 ↑ && 분모 ↓

대각선 줄이 홀수일 경우, 순번이 커질수록 분자 ↓ && 분모 ↑

 

 

 

🔗 소스 코드
HJ0216/TIL/BOJ

 

📚 참고 자료

[백준] 1193번 : 분수찾기 - JAVA [자바]