[백준] 분수 찾기 JAVA

백준_분수 찾기 문제
풀이 코드

처음에 숫자로 규칙을 찾아서 해봤다가, 생각치 못한 케이스들이 있어서 첫번째엔 틀렸다.
무작정 숫자로 규칙 찾는 것도 아닌 것 같다…

문제 예시가 좀 짧아서 어떤 방식인지 한눈에 보긴 어려웠다.

풀이

위와 같은 순서로 번호가 매겨진다.

이를 오른쪽으로 45도정도 돌려서 생각해보면 더 보기 편한데,
n번째 대각선에는 n번씩 분모가 1씩 증가하고, 분자가 1씩 감소하는 것을 볼 수 있다.

또 다음 대각선으로 넘어갈 때는 분모가 증가하거나 분자가 증가하는 것을 볼 수 있다.

그래서 이 방식과 똑같이 nFirst라는 분자와 nSecond라는 분모를 만들어서 증감시켰고,
nLoopCnt를 통해 몇 번째 대각선인지 파악해 n번만큼 증감을 반복시켜주었다.

증감 과정에서 만약 입력받은 수와 같은 수가 나오면 프로그램을 종료한다.

코드

import java.util.Scanner;

public class Main {
	static int nNum;
	static int nFirst;
	static int nSecond;
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		nNum = sc.nextInt();
		int nCnt = 1;
		nFirst = 1;
		nSecond = 1;
		int nLoopCnt = 0;
		
		while(true) {
			if(cntCheck(nCnt)) return ;

			//왼쪽에서 오른쪽으로 올라가는 대각선 루프
			for(int i = 0; i < nLoopCnt; i++) {
				nCnt++;
				nFirst--;
				nSecond++;	
				if(cntCheck(nCnt)) return ;
			}
			
			//오른쪽(가로)으로 한칸 이동
			nLoopCnt++;
			nCnt++;
			nSecond++;
			if(cntCheck(nCnt)) return ;
			
			//오른쪽에서 왼쪽으로 내려가는 대각선 루프			
			for(int i = 0; i < nLoopCnt; i++) {
				nCnt++;
				nFirst++;
				nSecond--;
				if(cntCheck(nCnt)) return ;
			}
			
			//아래(세로)로 한칸 이동
			nLoopCnt++;
			nCnt++;
			nFirst++;
			if(cntCheck(nCnt)) return ;
		}
	}
	public static boolean cntCheck(int nCnt) {
		if(nNum == nCnt) {
			System.out.println(nFirst + "/" + nSecond);
			return true;
		}
		else return false;
	}
}