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

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

1193번: 분수찾기

---

---

알고리즘

 

• T= 분모 + 분자
• 대각선 칸의 개수 = T - 1 = 현 대각선의 원소의 개수 = curr_crss_cnt
• 초록색
  T = 짝수 = (T % 2 == 0)
  대각선 칸의 개수 = 홀수
  좌측 하단에서 우측 상단 방향(↗)
• 분홍색
  T = 홀수 = (T % 2 == 1)
  대각선 칸의 개수 = 짝수
  우측 상단에서 좌측 하단 방향(↘)

---

풀이

1. Scanner

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int X = in.nextInt(); //입력값
        int curr_crss_cnt = 1, prev_cnt_sum = 0;
        //curr_crss_cnt: 현재 대각선(T) 원소의 개수 = T - 1
        //prev_cnt_sum: 현재 대각선(T) 이전의 모든 원소의 개수(1부터 T-1 대각선까지)
 
        while (true) {
            //현재 대각선 이전의 모든 원소의 개수 + 현재 대각선 원소의 개수로 범위 판별
            if (X <= prev_cnt_sum + curr_crss_cnt) {	
                if (curr_crss_cnt % 2 == 1) { //현 대각선 원소의 개수가 홀수일 때
                    System.out.print((curr_crss_cnt - (X - prev_cnt_sum) + 1) + "/" + (X - prev_cnt_sum));
                    break;
                    /*
                    X - prev_cnt_sum
                    입력값 - 현 대각선 이전의 모든 원소의 개수
                    
                    현재 대각선의 몇 번째 위치인지 알 수 있음
                    해당 숫자가 분자 or 분모 중 어디에 위치해있는지 확인
                    */
                    /*
                    curr_crss_cnt - (X - prev_cnt_sum) + 1
                    현 대각선 원소의 개수 - (입력값 - 현 대각선 이전의 모든 원소의 개수) + 1
                    
                    (X - prev_cnt_sum) + 1 에서 + 1 필수
                    (X - prev_cnt_sum) + ⬜ = T = curr_crss_cnt + 1
                    ⬜ = (curr_crss_cnt + 1) - (X - prev_cnt_sum)
                    ⬜ = curr_crss_cnt - (X - prev_cnt_sum) + 1
                    */
                } else { //현 대각선 원소의 개수가 짝수일 때
                    System.out.print((X - prev_cnt_sum) + "/" + (curr_crss_cnt - (X - prev_cnt_sum) + 1));
                    break;
                }
            } else {
                prev_cnt_sum += curr_crss_cnt;
                curr_crss_cnt++;
            }
        }
    }
}

 

2. BufferedReader

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int X = Integer.parseInt(br.readLine());
        int curr_crss_cnt = 1, prev_cnt_sum = 0;
        //curr_crss_cnt: 현재 대각선(T) 원소의 개수 = T - 1
        //prev_cnt_sum: 현재 대각선(T) 이전의 모든 원소의 개수(1부터 T-1 대각선까지)
 
        while (true) {
            //현재 대각선 이전의 모든 원소의 개수 + 현재 대각선 원소의 개수로 범위 판별
            if (X <= prev_cnt_sum + curr_crss_cnt) {	
                if (curr_crss_cnt % 2 == 1) { //현 대각선 원소의 개수가 홀수일 때
                    System.out.print((curr_crss_cnt - (X - prev_cnt_sum) + 1) + "/" + (X - prev_cnt_sum));
                    break;
                    /*
                    X - prev_cnt_sum
                    입력값 - 현 대각선 이전의 모든 원소의 개수
                    
                    현재 대각선의 몇 번째 위치인지 알 수 있음
                    해당 숫자가 분자 or 분모 중 어디에 위치해있는지 확인
                    */
                    /*
                    curr_crss_cnt - (X - prev_cnt_sum) + 1
                    현 대각선 원소의 개수 - (입력값 - 현 대각선 이전의 모든 원소의 개수) + 1
                    
                    (X - prev_cnt_sum) + 1 에서 + 1 필수
                    (X - prev_cnt_sum) + ⬜ = T = curr_crss_cnt + 1
                    ⬜ = (curr_crss_cnt + 1) - (X - prev_cnt_sum)
                    ⬜ = curr_crss_cnt - (X - prev_cnt_sum) + 1
                    */
                } else { //현 대각선 원소의 개수가 짝수일 때
                    System.out.print((X - prev_cnt_sum) + "/" + (curr_crss_cnt - (X - prev_cnt_sum) + 1));
                    break;
                }
            } else {
                prev_cnt_sum += curr_crss_cnt;
                curr_crss_cnt++;
            }
        }
    }
}

---

성능

• BufferedReader > Scanner

 

---

출처 : https://st-lab.tistory.com/74