백준 1193 분수찾기(Java)

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

1193번: 분수찾기

---

 

해석 및 팁

 

---

 

이문제는 지그재그의 규칙을 찾아내는것이 핵심이다.

그룹으로 나누어보면 1번그룹에는 1/1 2번그룹에는 1/2, 2/1 3번그룹에는3/1, 2/2, 1/3이 있다고하면

n번 그룹의개수는 n개이며 n이 홀수이면 분자가 1씩 줄어들고 분모가 1씩늘어나며

짝수이면 분자가 1씩 늘어나고 분모가 1씩 감소한다.

따라서 n번째 그룹까지의 수의 개수는 첫째항이 1이고 등차가 1인 등차수열의 합인 n*(n+1)/2 이므로

주어진수와의 차를 이용하면 해결할 수있다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int numerator = 0;          //분자
    int denominator = 0;        //분모
    int check = 0;
    int n = 0;
    int x = sc.nextInt();

    while(check < x) {
      n++;
      check = n*(n+1)/2;         //a=1, d=1 인 등차수열의 합 = n*(n+1)/2;
    }

    int gap = x - ((n-1)*n/2);
    
    if(n % 2 == 1) {
      numerator = n - gap +1;       //홀수행이면 분자가 1씩 줄어들고 분모가 1씩 늘어난다
      denominator = gap;            
    }

    else if(n % 2 == 0) {
      numerator = gap;              //짝수행이면 분자가 1씩 늘어가고 분모가 1씩 감소한다
      denominator = n - gap +1;
    }
    
    System.out.println(numerator+"/"+denominator);
  }  
}