[백준] 1193번 : 분수찾기 – JAVA [자바]

https://www.acmicpc.net/problem/1193

1193번: 분수찾기

 

---

• 문제

 

 

---

• 문제 풀이

백준 1193번 분수찾기는 브론즈 1 난이도의 수학 및 구현 문제이다. 이 문제에서는 우선 입력으로 정수 X가 주어진다. 그리고 문제에서 나와있는 것처럼 분수들이 나열되어있다.  1/1 → 1/2 → 2/1 → 3/1 → 2/2 →...

 

이 문제는 푸는 방식이 여러 개가 있을 수 있지만 이 글에서는 간단한 for-loop을 이용해서 풀어보려 한다.

 

이 문제는 분수들이 지그재그 같은 순서로 있다. 그리고 알아야 되는 것이 분수의 합이 2인 것은 1개 (1/1), 합이 3인 것은 2개 (1/2, 2/1)이고 나머지도 같은 패턴으로 이어진다. 이 점을 이용해서 문제를 접근해서 풀 것이다.

 

우선 주어진 X에서 1, 2, 3,... 을 X가 0 이하가 될 때까지 빼 줄 것이다. 즉, 처음에는 X에서 1을 빼주고, 그다음에는 X에서 2를 빼주고, 그다음에는 X에서 3을 빼주는 식으로 진행한다. 왜냐하면 1을 뺐을 때 X가 0 이하가 되면 바로 그 분수의 합이 2라는 것을 알게 되고 X에서 2를 뺐을 때 X가 0 이하가 되면 분수의 합이 3이라는 것을 알게 되기 때문이다. 이 빼는 수를 minus라고 하겠다. 이 minus는 분수의 합과도 같다.

 

그리고 그다음에는 이 문제에 나와있는 그림을 볼 것이다. 문제에 나와있는 그림을 보면 minus, 즉 분수의 합이 짝수이면 그림에서 위로 (↗) 올라가는 것을 확인할 수 있다. 그리고 minus, 즉 분수의 합이 홀수이면 그림에서 밑으로 (↙) 내려간다. 올라갈 때면 minus - 1 / 1에서 시작하고 배열에서 내려갈 때면 1 / minus - 1에서 시작한다. 이 점을 이용하면 문제를 풀 수 있게 된다.

 

자세한 코드는 밑에 있다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        int minus = 1;
        int where = -1;  //올라가는지 내려오는지 결정 
        while (x > 0) {
            x -= minus;
            minus++;
            where *= -1;
        }
        int start = 1;
        int end = minus - start;
        for (int i = 0; i < Math.abs(x); i++) {
            start++;
            end--;
        }
        //where가 1이면 올라가므로 1/x로 시작
        if (where > 0) {
            System.out.print(start + "/" + end);
        } else {
            //where가 -1이면 내려가므로 x/1로 시작
            System.out.print(end + "/" + start);
        }
    }
}