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

문제

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

주의

그림에 테이블이 있다고 해서 배열로 풀지 않아도 된다!

설명

문제를 살펴보면

테이블에 대각선 방향으로 분수가 채워지고 대각선 마다 분자와 분모가 커지고 작아지고를 반복하고 있다.

그림으로 정리하면 아래와 같다.

해당 대각선 수 만큼 분수의 갯수도 같다.
예) 세번째 대각선 = 대각선에 들어있는 분수 갯수

위 그림처럼 규칙이 보이면 다음과 같이 정리 할 수 있다.

위 규칙을 잘 기억하며 입력받을 수를 정하고 알고리즘을 짜보자

나는 8번을 입력했을때의 결과와 9번을 입력했을때의 결과를 다음과 같이 분석하였다.

짝수번째의 대각선의 알고리즘은

이와 동일하게 나왔고 홀수번째 대각선은 짝수번째 대각선 반대 이므로 분자와 분모의 위치를바꿔주면 된다.

정리하면 각 대각선의 알고리즘은 다음과 같다.

위 설명을 토대로 아래와 같은 코드가 나왔다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalNumber = 0;
        int cnt = 0;
        int num = scanner.nextInt();




        while(true) {
            totalNumber += cnt;
            if (num <= totalNumber) {

                if(cnt%2 ==0) {
                    System.out.println(num - (totalNumber - cnt) + "/" + ( totalNumber - num +1));
                }
                else {
                    System.out.println( (totalNumber - num +1) + "/" + (num - (totalNumber - cnt)));
                }
                return;
            }
            cnt++;
        }
    }
}