Blog

B1193 분수찾기

날짜 2024-03-27
사용 언어 Java
문제 유형 구현, 수학
정답률 51.595%
문제 URL https://www.acmicpc.net/problem/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번째 분수를 구하는 프로그램을 작성하시오.

제한사항 #
  • 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
  • 첫째 줄에 분수를 출력한다.

나의 풀이 #

분자+분모 해당 대각선에 있는 개수 총 개수
2 1 1
3 2 3
4 3 6
5 4 10
6 5 15
7 6 21
  • 만일 X가 9이면? 6~10이니까 4번째 대각선 상
  • 4번째 대각선이면? 분자+분모가 5
  • 10 - 9 = 1, 4 - 1 = 3 이니까 해당 대각선에서 3번째의 값
  • 대각선의 방향은? 합이 짝수면 분모가 오름차순
  • 9는 합이 홀수 -> 내림차순 -> 4,3,2,1
  • 분모는 2 분자는 3
import java.util.Scanner;  
  
public class Main {  
    public static void main(String[] args) throws Exception {  
        Scanner sc = new Scanner(System.in);  
        int X = sc.nextInt();  
  
        // 대각선 찾기  
        // 총 개수를 구하기 1, 3, 6, 10 ... 계차수열  
        int start = 1;  
        int startTerm = 2;  
        int total = start;  
        while (total < X) {  
            total = total+startTerm;  
            startTerm++;  
        }  
  
        // 대각선에서 몇번째인지 찾기  
        int A = total - X + 1;  
        int B = startTerm - (total - X) - 1;  
  
        // 대각선의 방향  
        String result = (startTerm%2 == 0)? A+"/"+B : B+"/"+A;  
        System.out.println(result);  
    }  
}
import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
  
public class Main {  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
  
        int X = Integer.parseInt(br.readLine());  
        br.close();  
  
        // 대각선 찾기    
// 총 개수를 구하기 1, 3, 6, 10 ... 계차수열    
int start = 1;  
        int startTerm = 2;  
        int total = start;  
        while (total < X) {  
            total = total+startTerm;  
            startTerm++;  
        }  
  
        // 대각선에서 몇번째인지 찾기    
int A = total - X + 1;  
        int B = startTerm - (total - X) - 1;  
  
        // 대각선의 방향    
String result = (startTerm%2 == 0)? A+"/"+B : B+"/"+A;  
        bw.write(result);  
  
        bw.close();  
    }  
}

실행결과

다른 사람의 풀이 #



관련개념 학습 #