백준(1193번, 분수찾기, 실버V)

문제 내용

문제 내용

---

제출한 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int x = Integer.parseInt(br.readLine());
        
        int count = 1, diagonal = 1; 
        while (count + diagonal <= x) {
            count += diagonal;
            diagonal++;
        }

        int up, down;
        int offset = x - count;

        if (diagonal % 2 == 0) {
            up = 1 + offset;
            down = diagonal - offset;
        } else { 
            up = diagonal - offset;
            down = 1 + offset;
        }

        sb.append(up).append("/").append(down);
        System.out.println(sb);
    }
}

---

후기

해당 문제는 실버 5? 난이도 였었지만 체감상 실버 5보다는 더 어렵게 느껴졌었다
그 이유는 단순한 수열이 아니고, 입력받은 분수의 이동 규칙을 찾아 풀이 방식을 적용하는데에 오래걸렸었다

분수 찾기 문제의 규칙

1. 분수들이 n번째까지 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → 1/3 → … 등의 규칙으로 나타남
2. 분모가 1이고 분자보다 작다면? 분자가 작아지면서 분모가 커진다
   ex) 1/3 → 2/2 → 3/1
3. 반대로 분자가 1이고 분모보다 작다면? 분모가 작아지면서 분자가 커진다
   ex) 3/1 → 2/2 → 1/3

1번째 대각선: 1
2번째 대각선: 1 + 2 = 3
3번째 대각선: 1 + 2 + 3 = 6

따라서 대각선 이동 규칙에다가 패턴을 적용해 번호가 1, 3, 6, 10, 15… 식으로 증가한다.
그래서 X번째 분수가 몇 번째 대각선에 위치하는지를 먼저 찾고, 이에 따라서 해당 대각선 내 위치를 계산해주는 걸로 문제를 풀이했다

위 규칙을 적용하기 위해서 먼저 수도 코드를 작성해보았다

---

작성한 수도코드

1. 분수 위치 X를 입력받기
2. 현재 대각선이 X보다 작은 경우, 대각선을 증가시키며 포함되는 분수 개수를 계산
3. 현재 대각선에서 몇 번째 위치인지 계산
4. 대각선이 짝수라면(오른쪽 아래로)
5. 대각선이 홀수라면(오른쪽 위로)

대각선이 짝수일때와 홀수일때의 계산

 if (diagonal % 2 == 0) { 
            up = 1 + offset;
            down = diagonal - offset;
        } else { 
            up = diagonal - offset;
            down = 1 + offset;
        }

짝수번째 대각선은 오른쪽 아래로 이동하며 분자가 증가, 분모가 감소
홀수번째 대각선은 오른쪽 위로 이동하며 분자가 감소, 분모가 증가

 

아래의 그림을 보면 이해가 더 쉬울거같다

참고한 내용

https://ghi512.tistory.com/50