[JAVA] 백준 1193번 분수찾기 : 부등식과 반복문 2

1193번: 분수찾기

 

 

1. 문제 추상화

 

수열문제는 규칙을 찾는 문제이다.

 

배열의 인덱스가 지그재그로 부여된다.

 

layer	인덱스
1층	1
2층	2 3 ( 하향 )
3층	4 5 6 ( 상향 )
4층	7 8 9 10 ( 하향 )
5층	11 12 13 14 15 ( 상향 )

 

이때, 입력된 인덱스가 가리키는 분수를 구하시오.

 

2. 알고리즘

 

1. 일정한 규칙에 따라 상향과 하향이 반복된다.

2. 입력값이 어느 범위에 포함되는지 알아야 한다.

3. 범위는 부등식이다.

4. 부등식 계산은 반복문을 사용한다. 

5. 범위를 파악하면, 범위의 최대 인덱스가 가리키는 분수를 구한다.

6. 범위의 최대 인덱스와 입력된 인덱스 사이의 차이를 통해 입력된 인덱스의 분수를 구한다.

 

3. 풀이

 

< 첫 번째 방법 >

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int value = sc.nextInt(); // 입력된 인덱스값
		int parent = 1; // 분모
		int child = 1; // 분자
		
		int max = 1; // 최댓값 
		int layer = 1; // 층
		
        // 입력된 인덱스가 포함된 범위 구하기
		while(value > max)
		{
			max = max + (++layer); // 
		}
		
		int dif = max - value; // 범위의 최대 인덱스와 입력된 인덱스 사이의 차이
		
		//layer가 짝수면 상향, 홀수면 하향
		if(count%2==0) {
			parent = 1 + dif;
			child = layer - dif;	
		}else {
			parent = layer - dif;
			child = 1 + dif;
		}
		
		System.out.println(child+"/"+parent);
	}

}

 

< 두번째 방법 >

 

layer	인덱스
1층	1
2층	2 3 ( 하향 )
3층	4 5 6 ( 상향 )
4층	7 8 9 10 ( 하향 )
5층	11 12 13 14 15 ( 상향 )

 

3층의 최댓값 : 6

4층 :  6+1, 6+2, 6+3, 6+4 

 

n층의 인덱스를 n-1층의 최댓값으로 빼면 인덱스가 1,2,3, ... , n 이 된다.

 

예를 들어, 입력값으로 14를 입력 받았다고 가정하자.

 

14는 5층에 포함된다.

4층의 최댓값은 10이다.

고로, 14는 5층의 4번째 값을 의미한다.

 

5층은 상향임을 고려하여 문제를 푼다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int value = sc.nextInt();
		int max = 1;
		int layer = 1;
        
		while( value > max ) {
			layer++;
			max = max + layer;
		}

		int preMax = max - layer; // 이전 최댓값 구하기
		int position = value - preMax; // 입력된 인덱스가 몇 번째 값인지 구하기

		//layer가 짝수면 하향, 홀수면 상향 
		// 하향 : 분자 = position, 분모 = (layer+1) - position
		// 상향 : 분자 = (layer+1) - position, 분모 = position
		
		int child = 1;
		int parent = 1;
		
		if(layer%2==0) {
			child = position;
			parent = (layer+1) - position;
		}else {
			child = (layer+1) - position;
			parent = position;
		}
		System.out.println(child + "/" + parent);
	}

}