백준 문제에 단계별로 풀어보기 중 기본수학1에 있는 분수찾기라는 문제이다.
분수찾기(1193)
문제 정보
처음엔 이문제가 브론즈가 맞나 생각했다. 그만큼 뇌가 굳어있었던거 같다...
문제
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.
X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.
처음엔 방향을 머리로만 그리다가 짜증나서 결국 펜을 꺼냈다.
입력
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
출력
첫째 줄에 분수를 출력한다.
해설
머리속으로 방향을 그리면 자꾸 까먹어서 그렸는데 나만 보기엔 아까워서 올린다.
더 어지러워보이는건 기분탓이다.
처음엔 각 순서의 규칙을 찾다가 이건좀 아니다 싶어서 좌뇌와 우뇌의 커플댄스로 겨우 다른 방향으로 보게 되었다.
위 그림에서 언뜻 보이는게 있을텐데 이 대각선이라고 하는 놈이 이전 포스팅에서 '겹'이랑 비슷한 역할을 한다는 것이다.
지금 조금 어지럽게 되어있어서 각 분수마다 번호를 붙이면 아래와같이 되는데
여기서 '겹'이라는 단어를 써보려고 한다.
1이 1겹 2 , 3이 2겹 4, 5 6이 3겹 ···
이라고 할떄 만약 14(5겹)에 도달하려면 몇 개의 숫자 즉, 몇 겹을 건너와야하는지만 구하면 쉬워진다.
자세히 보면 내가 '겹'이라고 표한한 곳과 대각선의 시작과 끝숫자를 보면 규칙이 생긴다.
예를 들어 26은 7겹에 포함되어있는 숫자인데 대각선에 시작과 끝이 7/1 에서 1/7이다.
양 끝의 숫자 규칙이 무슨 관련이 있나 싶었지만 이는 양 옆의 숫자가 대칭이라는 점을 생각하면 좋다.
26에다가 7겹의 시작숫자인 22를 빼면 4라는 오차가 나오는데 이를 시작지점 분수인 7/1 양쪽에 각각 더하고 빼면 (7-4)/(1+4) = 3/5라는 숫자가 나온다.
이때 조심해야할 점이 이 숫자는 시작하는 숫자를 기준으로 잡았다는 점이다.
따라서 시작하는 지점의 분수가 무엇인지 알아야 한다는 건데 이는 현재 겹이 홀수인지 짝수인지만 알면 위에서 아래인지 아래에서 위인지가 나오게 된다.
그렇다면 이제 내가 말한 '겹'이라는 놈으로 이번 문제의 정답을 알 수 있다는 건데 이 겹을 어떻게 구하면 될지도 생각해야한다.
이부분도 간단한것이 겹의 숫자들이 1 + 2 + 3 + 4 + ··· 이다. 즉, 1씩 증가하는 등차수열이라는 말이다.
따라서 1부터 2, 3, 4 ··· 차례로 더하면서 주어지는 X와 비교해 합이 X보다 커지면 멈추는 식으로 겹을 구할 수 있다.
순서
- 현재 숫자가 몇번째 등차수열인지 찾기
- 등차수열의 시작숫자와 X의 오차 구하기
- 오차를 시작 분수와 연산하여 분수 구하기
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class _1193 {
//분수찾기
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int X = Integer.parseInt(br.readLine());
int distence = 0;
int i = 0;
while(distence < X){
distence += i++;
}
int dif = X - (distence - (i -1))-1;
i--;
//위 연산은 while문 통과시 이미 다음겹을 보고있기 때문에 보정이 필요
if((i-1)%2 == 0){
System.out.println((i - dif )+ "/" + (1 + dif));
}else{
System.out.println((1 + dif) + "/" + (i - dif));
}
}
}
