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();
}
}
다른 사람의 풀이 #