📌 문제

[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은 처음부터 분모와 분자가 모두 1이므로 그 옆의 1/2로 넘어가고, 대각선 아래의 2/1 을 찾아간 후 다시 그 아래 수인 3/1로 넘어가서 대각선 위로 거슬러 올라가 1/3을 찾고, ...

➡️ 마지막 지점이 1/분모 (홀수)는 옆으로 가서 분모+1, 분자/1 (짝수)는 아래로 가서 분자+1 수행

• 대각선 아래 이동 (파란색, 짝수) : 분자+1/분자-1
• 대각선 위로 이동 (초록색, 홀수) : 분자-1/분모+1

✅ 위 식을 어떻게 코드로 쓸 수 있을까 하다가 그냥 내가 찾은 규칙들을 몽땅 때려 넣었다,, 규칙이 크게 홀수/짝수로 구분되므로 if ~ else문을 사용해서 각 조건 별 증감식을 수행하도록 함. 이 때, x =1 인 경우에는 반복문을 돌지 않고 초기 조건을 그대로 출력하므로, for문을 x-1번 반복 수행.

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int nume = 1; // 분자
		int deno = 1; // 분모
		int num = 1;
		int x = Integer.parseInt(br.readLine());
		
		if(x > 1) {
			for(int i=0;i<x-1;i++) {
				if(num % 2 != 0) { // 홀수
					if(nume == 1) deno = ++num; // 옆
					else {
						nume--; deno++;
					}
				} else { // 짝수
					if(deno == 1) nume = ++num; // 아래
					else {
						nume++; deno--;
					}
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(nume).append("/").append(deno);
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

➕ 내가 너무 어렵게 생각한 것 같아서 구글링 해보니 역시나,, 내가 빙빙 꼬아서 생각하고 있었다,,

기본적으로 홀수일 때는 대각선 위, 짝수일 때는 대각선 아래 방향으로 이동하는 것은 같은데, 나처럼 모든 경우의 수를 냅다 조건으로 걸어서 for문을 돌리는 게 아니라, 대각선의 개수를 구해서
해당 대각선에서 조건을 판별하여 분자와 분모를 쉽게 구하는 방법도 있었다,, 메모리랑 시간도 엄청 단축됨,,

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int x = Integer.parseInt(br.readLine());
        int line = 1;

        while(x>line){
            x-=line;
            line++;
        }
        
        StringBuilder sb = new StringBuilder();
        if(line % 2 == 0) sb.append(x).append("/").append(line-x+1);
        else sb.append(line-x+1).append("/").append(x);
        bw.write(sb + "");
        
		br.close();
		bw.close();
	}
}