백준 1193번 분수찾기 풀이

알고리즘 문제를 푸는 첫 단계는 언제나 규칙성을 찾아보는 것이다. 단순 무식하게 배열을 만들어서 풀어도 되지만, 시간도 오래걸리고 비효율적이다. 따라서 규칙을 찾고 그 규칙에 따라 수학적으로 풀어보자.

설명을 보고 규칙을 찾아보면

이런 식으로 분수를 읽는것 을 알수 있다.

또한 시작하는 분수의 분모와 분자는 n번째 화살표(위에서 작은 순서부터)이면 분모 혹은 분자도 n인것을 알 수 있다. 그리고 n+1번 분수는 n번 분수보다 분자가 1작고 분모는 1이 크다.(하나의 화살표에서만 해당)

 

풀이

규칙

• n+1번 분수는 n번 분수보다 분자가 1작고 분모는 1크다.
• n번쨰 화살표의 각 끝부분 분수는 분자 or 분모가 n이다.
• 지그재그이므로 가장 작은 화살표 를 1번이라 하고, 그 다음 화살표를 2번이라 할때 , 홀수번째 화살표는 위로 읽고 짝수번째 화살표는 아래로 읽는다.

n번째 분수의 위치를 구하기 위해서 n번째 화살표가 몇번부터 몇번까지의 분수를 포함하고 있는지 알아야 한다. n번째 화살표는 n개의 분수를 가지고 있으므로 1+2+3+4.....을 해서 더한 합이 구하려는 n번째 분수의 n보다 크면 해당 화살표에 그 분수가 포함되어 있는 것을 알 수 있다.

그리고 가장 처음과 가장 마지막은 번호를 알 수 있으므로 그것을 이용해서 n번째의 분수를 찾으면 된다.

문제를 풀다보니 굳이 추가 안해도 되는 함수가 들어가 있는다...

import java.util.Scanner;

public class Main {
	
	static int calculateTurn(int number) {
		int n=1;
		int answer=0;
		if(number==1)
			return 1;
		while(true) {
		
		if(number<=answer)
			return n;
		else {
			answer=0;
			n++;
			for(int i=1;i<=n;i++)
				answer+=i;
		}
		}
	}
	static int calculateAnswer(int number) {
		int n=1;
		int answer=0;
		if(number==1)
			return 1;
		while(true) {
		
		if(number<=answer)
			return answer;
		else {
			answer=0;
			n++;
			for(int i=1;i<=n;i++)
				answer+=i;
		}
		}
	}

	public static void main(String[] args) {
		int number,first,last; //구하려는 분수, 첫번째 분수, 마지막 분수
		int turn;
		int answer;
		int son,parents; //분자, 분모
		Scanner scanner=new Scanner(System.in);
		number=scanner.nextInt();
		turn=calculateTurn(number);
		answer=calculateAnswer(number);
		last=answer;  //마지막 분수
		first=answer-turn+1; //첫번째 분수
		if(turn%2==0) {
			parents=turn;
			son=1;
			for(int i=first;i<=last;i++) {
				if(number==i) {
					System.out.println(son+"/"+parents);
					break;
				}
				else {
					parents-=1;
					son+=1;
				}
			}
		}
		else {
			parents=1;
			son=turn;
			for(int i=first;i<=last;i++) {
				if(number==i) {
					System.out.println(son+"/"+parents);
					break;
				}
				else {
					son-=1;
					parents+=1;
				}
			}
		}
	}

}