[알고리즘] 백준 - 1193번 분수찾기

오랜만에 작성하는 알고리즘 오답노트...(진짜 전혀 이해가 안되서 정리하려고 한다)

문제

처음에는 for문을 통해 대각선을 전부 조회해서 해당하는 입력값에 대한 결과를 출력하려 했는데, 전혀 어떻게 작성해야 할지 감이 잡히지 않았다.

발견한건 각 대각선 (홀수, 짝수번째) 대각선의 분모와 분자의 합이 대각선끼리 동일하다는것
1/1 -> 1/2 -> 2/1 순서만 봐도 2, 3 으로 값이 같다.

분모,분자의 합을 C라고하고 출력하는 순서는 C가 홀수 일경우는 아래방향 대각선으로 짝수일 경우에는 위로 향한다 즉 C % 2 가 조건이 된다.

또한 다른 관점으로 대각선을 봤을 때 각 분모와 분자는 오른쪽 아래로 갈수록 1씩 커진다.
ex) ( 1/1 , 2/2, 3/3 ) , (2/1 , 3/2) 처럼 이러한 조건으로 출력하면 된다.

코드로 말하면 아래와 같다.

정답 코드

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		int X = in.nextInt();
 
		int C = 1, prev_count_sum = 0;
 
		while (true) {
        
			if (X <= prev_count_sum + C) {	
				
				if (C % 2 == 1) {	
					System.out.print((C - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
					break;
				} 
				
				else {	 
					System.out.print((X - prev_count_sum) + "/" + (C - (X - prev_count_sum - 1)));
					break;
				}
 
			} else {
				prev_count_sum += C;
				C++;
			}
		}
	}

이 처럼 대각선의 총 칸수를 C라고 하고 대각선의 총갯수 합을 2로 나누었을 때 조건을 나누어서 출력하게 했다.

사실 1시간 넘게 고민해도 풀지 못해서, 블로그를 봤는데 이 풀이를 이해하는데도 오래걸렸다.. (사고력이 부족하다,,,)

참고 블로그

참고 블로그: https://st-lab.tistory.com/74