문제
무한히 큰 배열에 다음과 같이 분수들이 적혀있다.
| 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)가 주어진다.
출력
첫째 줄에 분수를 출력한다.
<작성 답안>
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int X = s.nextInt();
int[] arr = new int[X];
int[] arr2 = new int[X];
int sum = 0;
for(int i=0; i < arr.length; i++){ //분모와 분자를 더한 값을 등차수열로 배열에 집어넣음
sum = sum + i;
int b =1+ sum;
for(int j=0; j<sum; j++){
arr[b+j]=i+2; //i+2 = 분모와 분자의 합인 수.
if((i+2)/2 ==0) { // 1,3,5줄 ... 홀수 줄(왼쪽에서 오른쪽)
for(int k=1; k<=i+2;k++) {// 분자들이 가장 큼에서 작은 순
arr[b+j]=i+2-k;
}
}
else { // 2,4,6,.... 짝수 줄 (오른쪽에서 왼쪽)
for(int k= i+1; k>=1;k--) {// 분자들이 가장 작음에서 큰 순
arr[b+j]=i+2-k;
}
}
}
}
for(int i=0; i < arr2.length; i++){ //분모와 분자를 더한 값을 등차수열로 배열에 집어넣음
sum = sum + i;
int b =1+ sum;
for(int j=0; j<sum; j++){
arr2[b+j]=i+2; //i+2 = 분모와 분자의 합인 수.
if((i+2)/2 !=0) { // 2, 4, 6줄
for(int k=1; k<=i+2;k++) {// 분모들이 가장 큼에서 작은 순
arr2[b+j]=i+2-k;
}
}
else { // 1,3,5줄
for(int k= i+1; k>=1;k--) {// 분모들이 가장 작음에서 큰 순
arr2[b+j]=i+2-k;
}
}
}
}
System.out.println(arr[X+1]+"/"+arr2[X+1]);
}
}
(내 사전 설계도)
줄 : 박스 갯수 : 둘을 더한 값
1 : 1 ->
2 : 2 <- 분모 큼 줄+1
3 : 3 -> 분자 큼
4 : 4
5 : 5
6 : 6
분모든 분자든 맨 앞자리는 그 줄값.
scanner 입력받는값.
int[] arr = new int[s.next()];
for(int i =0; i<
1+2+3+4
j 반복문 0 , 01, 012, 0123
for(int i=0; i < arr.length; i++){
sum += i
int b =1+ sum
for(int j=0; j<sum; j++){
a[b+j]=i+2
}
}
i+2 b i
2 1 0번째 -> 분자큼
33 23 1번째
444 456 제일 큼-> 제일 작음
5555 7 8 9 10
66666
777777
1 1+0 0번째
2 1+1 1번째
4 1+3 2번째
7 1+6 3번째
11 1+ 10 4번째
a = i+(i+1)
i=1 ~
sum += i
b=1+ sum
-> 컴파일하면 예외 오류가 떠서 포기했다. 표면적으로 드러난 에러는 없다.
-> 게다가 시간초과이다.
-> 3시간을 붙들고 앉아있었고, 못 맞췄지만, 머리는 의미있게 엄청 굴려본 것 같다.
결국 끝까지 뭔가 내 식대로 만들어내긴 했다. 이게 더 중요하다.
<정답>
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int X = in.nextInt();
int cross_count = 1, prev_count_sum = 0;
while (true) {
// 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
if (X <= prev_count_sum + cross_count) {
if (cross_count % 2 == 1) { // 대각선의 개수가 홀수라면
// 분자가 큰 수부터 시작
// 분자는 대각선상 내의 블럭 개수 - (X 번째 - 직전 대각선까지의 블럭 개수 - 1)
// 분모는 X 번째 - 직전 대각선까지의 블럭 개수
System.out.print((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
break;
}
else { // 대각선상의 블럭의 개수가 짝수라면
// 홀수일 때의 출력을 반대로
System.out.print((X - prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
break;
}
} else {
prev_count_sum += cross_count;
cross_count++;
}
}
}
}
(해설)
앞서 언급했듯이 분수를 찾는 것은 그렇게 어려운 문제가 아니다.
어떤 칸에 어떤 분수인지는 그림만 보더라도 바로 나온다.
분모 값과 분자 값의 합을 T 라고 할 때 다음과 같은 규칙이 생긴다.
그리고 대각선 칸의 개수는 T - 1 개다.
그러면, X 번째의 분수는 어떻게 찾아야 하는가가 문제다.
문제에서 순서는 다음과 같다고 명시되어 있다.
1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> …
즉, 위 그림으로 치면 다음과 같다.
파란색 ( T 가 짝수, 또는 대각선 칸의 개수가 홀수 ) 일 때는 왼쪽 아래에서 오른쪽 위 방향 ( ↗︎ ) 으로 진행되고,
빨간색 ( T 가 홀수, 또는 대각선 칸의 개수가 짝수 ) 일 때는 오른쪽 위에서 왼쪽 아래 방향 ( ↙︎ ) 으로 진행된다.
즉, T % 2 가 0 일 때는 대각선 위 방향, 1 일 때는 아래 방향으로 진행된다는 것.
그럼 우리가 이용할 변수는 다음과 같다.
- 입력받을 X 값
- 해당 범위의 대각선 칸 개수 ( cross_count )
- 해당 대각선 직전 대각선 까지의 칸의 누적 합 ( prev_count_sum )
이렇게 3 개를 이용하여 X 값이 해당 범위의 값이 나올 때 까지 반복하고,
만약 해당 범위의 값이라면
대각선의 개수가 홀수인지, 짝수인지 판별하여 해당 대각선의 첫 원소와 X, 대각선의 개수를 이용하여 분모 분자 값을 구해준다.
<수정 보완>
접근법, 특히 찾아낸 규칙은 동일하다. 차이점은 분자는 대각선상 내의 블럭 개수 - (X 번째 - 직전 대각선까지의 블럭 개수 - 1)
// 분모는 X 번째 - 직전 대각선까지의 블럭 개수
이런식으로 구했고, 나는 분모 분자의 합을 통해 그 분모 분자를 반복문으로 하나씩 일일히 빼는 식으로 했다.
직전 대각선까지의 블럭 개수를 통해 내가 쓴 등차수열 방식으로의 접근을 확줄인것이 시간을 줄인 차이라 하겠다.
너무 복잡하게 내가 식을 짠 듯싶다.. ㅠ
정답 및 풀이 출처: https://st-lab.tistory.com/74
'📟java > 백준' 카테고리의 다른 글
| 백준 2839 자바 (0) | 2022.11.14 |
|---|---|
| 백준 10250 자바 (0) | 2022.11.14 |
| 백준 1712 자바 (1) | 2022.11.13 |
| 백준 2941 자바 (0) | 2022.11.12 |
| 백준 2908 자바 (0) | 2022.11.12 |