[백준] 1193번 : 분수찾기 - Java

문제

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

지그재그 순회 방식으로 n번째 분수를 찾는 문제입니다. 분수는 대각선 방향으로 순회하며, 홀수 번째 대각선에서는 오른쪽 위 방향(↗)으로, 짝수 번째 대각선에서는 왼쪽 아래 방향(↙)으로 진행됩니다.

접근 방법

• 대각선 번호와 누적 칸 수 계산: n이 속하는 대각선 번호와 해당 대각선까지의 칸의 누적 합을 구합니다.
• 짝수/홀수 대각선 구분: 짝수 대각선인 경우와 홀수 대각선인 경우에 따라 분자와 분모를 계산합니다.

구현

• 대각선 번호와 누적 칸 수 계산:
  • crossCount는 현재 대각선 번호를 나타냅니다.
  • square는 해당 대각선까지의 칸의 누적 합을 나타냅니다.
  • n이 square보다 작아질 때까지 대각선 번호를 증가시키고 누적 칸 수를 업데이트합니다.
• 짝수/홀수 대각선 구분:
  • crossCount가 짝수인 경우 분자는 crossCount - (square - n)이고 분모는 (square - n) + 1입니다.
  • crossCount가 홀수인 경우 분자는 (square - n) + 1이고 분모는 crossCount - (square - n)입니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int crossCount = 0; // 대각선 번호
        int square = 0; // 대각선 번호 까지 칸의 누적 합 1,3,6,10,15,...

        while(square < n) {
            crossCount++;
            square += crossCount;
        }

        if(crossCount%2==0){
            int numerator = crossCount - (square - n); // 분자
            int denominator = (square - n) + 1; // 분모
            System.out.println(numerator + "/" + denominator);
        }else {
            int numerator = (square - n) + 1; // 분자
            int denominator = crossCount - (square - n); // 분모
            System.out.println(numerator + "/" + denominator);
        }

    }
}

 

메모리:18396kb 시간:232ms