오늘의 알고리즘 공부는 백준의 1193번이다.

백준 사이트에서 문제보기

🐱‍👓목차

• 문제
• 문제 이해하기
• 규칙 찾기
• 코딩 적용하기

문제는 다음과 같다.

문제는 이렇게 된다.

문제를 푸는 방법을 통해서 보자!

📌문제 이해하기

문제를 보면 다음과 같은 흐름으로 출력이 된다는 것을 알 수 있다.

section마다 index가 있으며, 위의 화살표 순서로 1부터 1씩 증가한다.

예를 들어, 8을 입력하면 화살표 순서대로 1씩증가하며 보면 "2/3"이 출력되는 것을 알 수 있다.

📌규칙 찾기

🔎진행 흐름 찾기

표를 보면서 진행방향을 체크해보면 짝수는 아래에서 위로, 홀수는 위에서 아래로 진행되는 것을 알 수 있다.

🔎라인 찾기

먼저 몇번째 라인인지 아는 것이 출발점이다.

편하게 찾기 위해서 "입력: 8"로 예를 들면,
8은 2/3이며, 4라인에 존재한다는 것을 알 수 있다.

8 -> 4라인 이라는 것을 어떻게 알 수 있을까?

내가 생각한 방법은 다음과 같다.

각 라인이 가질 수 있는 구역(section)의 수는 1부터 1씩 증가하는 등차수열이다.

그럼 8에다가 각 라인이 가질 수 있는 구역 수를 계속 빼준다. 그러다가 음수, 0이 나오는 부분이 8이 존재하는 라인이다.

8 - 1 = 7 (라인 1)
8 - 3 = 5 (라인 1+2)
8 - 6 = 2 (라인 1+2+3)
8 - 10 = -2 (라인 1+2+3+4) - 라인 4에 8이 포함

🔎인덱스 찾기

라인찾기는 성공했다.
하지만 "8"은 4라인의 2번째 인덱스인데..
어떻게 2번째 인덱스라는 것을 알 수 있을까?

조금만 눈치가 있으면 알 수 있다!
방금 라인을 구하는 과정중에, 음수 또는 0 값이 나오기 전에 계산해준 값이 인덱스이다!!

예를 들면, 8은
8 - 1 = 7 (라인 1)
8 - 3 = 5 (라인 1+2)
8 - 6 = 2 (라인 1+2+3) - 인덱스 2
8 - 10 = -2 (라인 1+2+3+4) - 라인 4에 8이 포함

🔎인덱스에 따른 출력값 계산하기.

라인에 따른 분수의 시작을 보면,

짝수 라인은 분모가 라인 수, 분자가 1
홀수 라인은 분모가 1, 분자가 라인 수
인 것을 알 수 있다.

그리고

인덱스가 증가함에 따라,
짝수 라인은 분모가 -1, 분자가 +1
홀수 라인은 분모가 +1, 분자가 -1
인 것을 알 수 있다.

🔎최종적인 흐름 예상

1. 숫자를 입력받는다.
2. 입력받은 숫자가 속한 라인을 구한다.
3. 해당 라인의 인덱스 값을 구한다.
4. 분자, 분모를 인덱스에 따른 값을 계산한다.

📌코드 적용하기

🔎라인 찾기, 인덱스 찾기

		//라인
		int line = 1;
        
        // 계산에 필요한 임의의 수
		int temp = 1;
        
        // 인덱스
		int indexNumber = 0;
        
		while(true) {
			
            //음수값이 되었을 때, 반복문 종료
			if(receiveNumber - temp <= 0) {
				break;
			}
			
            //음수값이 아니므로, 추가적 계산을 위한 작업
			receiveNumber -= temp;
			indexNumber = receiveNumber;
			temp++;
			line ++;
			
		}

🔎인덱스에 따른 출력값 찾기

		int firstNumber = 1;
		int secondNumber = line;
		int i = 0;
        
		while(i  < indexNumber - 1) {
			firstNumber ++;
			secondNumber --;
			i++;
		}

나는 firstNumber = 분자, secondNumber = 분모로 정해놓고 했다.
홀수와 짝수를 나누지 않은 이유는, 홀수 일 경우에는 분자 분모를 바꿔서 출력하면 되기 때문에 구분하지 않았다.

📌최종코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
			
		Scanner sc = new Scanner(System.in);
		
		int receiveNumber = sc.nextInt();
		sc.close();
		
		int line = 1;
		
		int temp = 1;
		int indexNumber = 0;
		while(true) {
			
			if(receiveNumber - temp <= 0) {
				break;
			}
			
			receiveNumber -= temp;
			indexNumber = receiveNumber;
			temp++;
			line ++;
			
		}
		
		System.out.println(findNumber(line, indexNumber));
	}
	
	public static String findNumber(int line, int indexNumber) {
		
		int firstNumber = 1;
		int secondNumber = line;
		int i = 0;
		while(i  < indexNumber - 1) {
			firstNumber ++;
			secondNumber --;
			i++;
		}
		//홀수일 경우
		if(line % 2 == 1) {
			
			return ""+secondNumber + '/' + firstNumber;
		}
		
		return ""+firstNumber + '/' + secondNumber;
	}

}