1193번 분수찾기
https://www.acmicpc.net/problem/1193
아래 그림과 같은 무한한 배열이 주어진다.
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로
차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 할때 X번째 분수를 구하는 문제이다.
입력 범위가 X(1 ≤ X ≤ 10,000,000)로 꽤 넓고 시간제한은 0.5초로 짧다.
처음에 지그제그가 무슨 말이지 하고 직접 그림판으로 그려보니 이해가 되었다.
이 문제를 단순히 보이는 대로 배열로 풀었다간 무조건 시간 초과가 날 것이다.
그리고 지그제그로 되어있어 어떤 특정한 패턴을 찾아야 했다.
그래서 일단 지그제그 순서대로 표를 만들어서 써보았다.
| 순번 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1/1 | ||||
| 2 | 1/2 | 2/1 | |||
| 3 | 3/1 | 2/2 | 1/3 | ||
| 4 | 1/4 | 2/3 | 3/2 | 4/1 | |
| 5 | 5/1 | 4/2 | 3/3 | 2/4 | 1/5 |
이렇게 하나하나 작성하고 보니 어떤 특정한 패턴이 보이기 시작했다.
1. 홀/짝수 번호에서 분모와 분자의 순서가 뒤바뀐다.
2. 최대 분모와 분자는 순번을 넘어가지 않는다. ex) 3번은 3을 넘지않음
3. 분모와 분자는 서로 1씩 늘어나거나 줄어든다.
이렇게 세가지 규칙을 찾아내었고 이걸 코드에 어떻게 적용할까 고민하였다.
일단 고려사항으로는
1. for문의 반복횟수를 최대한 줄여서 시간 복잡도를 줄여야 하고,
2. 홀/짝수 번호에서 분모와 분자의 위치를 서로 바꾸고 1씩 줄이거나 늘려야 한다.
그렇게 고민하다 생각해낸 방법은
해당 순번에서 최대/최소 값을 구해서 if문으로 분리하고, 연산해주는 방법을 떠올렸다.
그리고 홀/짝은 순번의 나머지 값을 비교하는 방식으로 분리하였다.
이제 코드로 구현해보면...
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
int sum = 0;
while(true){
if (n==1){
System.out.println("1/1");
break;
}
if(n <= sum){
if (count%2==0){ // 짝수
System.out.printf("%d/%d",n-(sum-count),count-(n-(sum-count))+1);
break;
}
else{ // 홀수
System.out.printf("%d/%d",count-(n-(sum-count))+1,n-(sum-count));
break;
}
}
count++; // 카운트
sum += count; // 최대값
}
}
}
while문으로 무한 반복을 돌리고
1의 경우에는 예외처리를 해주었고
count와 sum을 만들어서 각 순번과 최대값을 구할 수 있게 했다.
중간에 수식이 꽤 난잡한데 풀어서 정리하자면
(sum-count)
- 최대값과 카운트를 빼서 해당 순번의 최소값을 구했다.
n-(sum-count)
- n과 최소값을 빼서 분모/자를 만들었다.
count-(n-(sum-count))+1
- 분/모자 값에 순번을 빼서 역의 값이 나오도록 했다. 1로 값을 세부 조정했다.
이렇게 쓰고나니깐 뭔가 더 많이 복잡한데 일단 문제를 해결하긴 했다.
메모리는 17748 kb , 시간은 176ms가 걸렸다.
역시 문제를 풀때는 종이에 한번 써보는게 생각을 정리하는데 많은 도움이 되는것 같다.