백준 온라인 - 수학1 - 분수찾기

문제 정보

• 백준 알고리즘
• 단계 : 수학 1
• 문제 번호 : 1193
• 링크 : https://www.acmicpc.net/problem/1193

문제

풀이

• 출발점 1/1 부터 이동하는 경로는 요약하면 1 -> 2 -> 3 -> 4 로 확장되는 패턴을 가진다.
• 1 -> 2 -> 3 -> 4 확장 중 가로는 분자가 확장된 숫자로 표현되고, 세로는 분모로 확장된 숫자가 표현된다. 확장된 숫자 = 라인 번호
• 라인 번호가 짝수면 가로에서 세로 방향으로 내려오고,
  라인 번호가 홀수면 세로에서 가로 방향으로 올라가며 이동한다.
• 확장된 라인 번호 까지의 모든 칸의 숫자는 라인 번호까지의 모든 라인 숫자의 합
  • ex. 4번 라인까지의 모든 칸 수는. 1 + 2 + 3 + 4 = 10 칸.
  • 이를 재귀 함수화하면 f = f(x-1) + x
• 1부터.. n 까지 라인 번호 칸수의 합 N 을 구하다가 N 이 입력된 이동 값 X 보다 커지면
n 은 이동이 마무리되는 현재 라인 번호이고,
  X - (n-1 라인 의 칸 수) 는 현재 라인 첫재칸에서부터 이동해야 할 횟수 가 된다.
• 라인 홀짝 여부에 따라 분모 or 분자를 라인 번호로 설정하고 조건에 따라 분모 분자를 더하거나 빼면서 이동

재귀 보완

• 재귀함수 f =f(x-1) + x 를 그대로 사용하면 1부터 입력값까지 전부 계산이 들어가 비효율적이다.
• 입력값이 양수일 경우 (1 + 입력값) x (입력값 / 2) 가 결국 1~n 까지의 합이되므로, 입력값이 커질수록 효율적이 될 것
  • ex. 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 10 = 55.
  • (1 + 11) * (10 / 2) = 55

예시

• 이동 값 X = 13
• 1 + 2 + 3 + 4 + 5 = 15. 라인 번호는 5
• 15 - 13 = 2 = 5번 라인에서 이동해야 할 횟수
• 5/1 -> 4/2 (1) -> 3/3 (2) - > 3/3

코드

import java.util.Scanner;

public class Main {


    public static int sumOfNumber(int input) {
        if (input <= 1)
            return input;

        if (input % 2 == 0)
            return (input + 1) * (input / 2);

        return sumOfNumber(input - 1) + input;
    }

    public static String solve(int input) {

        int prevSum = 1;
        int currentSum = 1;
        int curIt = 0;

        for (int i = 0; currentSum < input; i++) {
            curIt = i;
            prevSum = currentSum;
            currentSum = sumOfNumber(i);
        }

        int minusValue = input - prevSum;
        boolean isOdd = curIt % 2 == 0;

        int child = isOdd ? 0 : curIt + 1;
        int mother = isOdd ? curIt + 1 : 0;

        for (int i = 1; i <= minusValue; i++) {
            if (isOdd) {
                mother--;
                child++;
            } else {
                mother++;
                child--;
            }
        }

        return child + "/" + mother;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int input = scanner.nextInt();
        System.out.println(solve(input));
    }
}