오늘의 알고리즘 공부는 백준의 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
인 것을 알 수 있다.
//라인
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;
}
}