[BOJ] 백준 1193번: 분수찾기 _자바(JAVA)
1. 문제
https://www.acmicpc.net/problem/1193
2. 접근 및 해결
2-1) 접근
문제를 해결하기 위해 총 4가지를 신경써야합니다.
풀이 이해를 쉽게 하기 위해 Input을 8이라 가정, Output인 2/3을 찾아야하는 경우를 알아보겠습니다.
아래의 노트를 띄워놓고 설명을 봐주세요!
1. 방문 순서
방문 순서는 문제에서 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서라고 나와있습니다.
이를 쉽게 다시 생각해보면,
1/1,
1/2 -> 2/1,
3/1 -> 2/2 -> 1/3 의 순서로 파란색 대각선 막대기처럼 계속 이동하는 것을 알 수 있습니다.
그리고 우리가 찾아야하는 8번째 값은 이렇게 따라가다보면 2/3임을 알 수 있습니다.
2. 개수
개수는 하나의 파란색 대각선 막대기 당 몇 개의 분수들이 들어가있는지를 나타냅니다.
우리가 찾는 8번째 값인 2/3은 개수=4임을 알 수 있습니다.
개수라고 하기에는 헷갈리니까, 4번째 줄이라고 생각합시다.
3. 대각선의 합
각각의 대각선의 합은 개수+1임을 볼 수 있습니다.
우리가 찾는 8번째 값인 2/3은 합이 5인 구간에 위치하고 있습니다.
4. 홀수번째 줄? 짝수번째 줄?
위에서 2. 개수를 설명할 때 4번째 줄이라고 생각하자고 했었습니다.
굳이 그렇게 한 이유는 방문순서에서 쓰였던 파란색 대각선 막대기를 기준으로 1줄씩 봤을 때,
홀수번째는 감소/증가하는 형태를 띄고 있고, 짝수번째는 증가/감소하는 형태를 띄고 있습니다.
우리가 찾는 8번째 값인 2/3은 증가/감소하는 구간에 위치하고 있군요.
좀 더 쉽게 설명하자면,
4번째 줄은 1/4 -> 2/3 -> 3/2 -> 4/1입니다.
분자는 1 -> 2 -> 3 -> 4로 증가하고 있고, 분모는 4 -> 3 -> 2 -> 1의 형태로 감소하고 있지요.
2-2) 해결
이제 신경써야하는 4가지에 대해 모두 알게 되었는데, 그래서 코드로 어떻게 해결할지를 알아봅시다.
예시 Input인 X는 8입니다.
즉, 8 = 1+2+3+2이지요.
왜 마지막에 +2를 해두었냐? 우리는 8=(1+2+3)+2로 보아야합니다.
앞에서 개수는 1, 2, 3, 4로 증가함을 알게 되었는데 여기서 괄호 안에 있는 값의 수가 (개수값-1)입니다.
왜 -1이냐면 괄호 밖에 있는 +2로 인해 개수값이 +1이 되기 때문이지요.
결국 우리가 찾는 2/3은 4번째에 위치하고,
앞서 알아본 4가지를 종합해서 보았을 때 2/3은 합이 5인 구간에서 2번째 순서임을 알 수 있습니다.
합이 5인구간에서 2번째 순서란? (+개수 값이 짝수(4)임)
1/4, 2/3, 3/2, 4/1에서 2/3 임을 알 수 있습니다.
3. 코드(JAVA)
코드와 관련된 설명은 상세히 주석으로 달아두었습니다.
위에서 작성한 접근 및 해결을 읽어보시고 읽어주세요!
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int X = Integer.parseInt(br.readLine());
int num = 0;
// X가 1이거나 2인 경우 아래의 for문 내 if문에 접근하지 못하므로 따로 처리
if(X==1) {
bw.write("1/1");
} else if(X==2) {
bw.write("1/2");
}
// ex) X=8인 경우에 대해 생각해보면
for(int i=1; i<X; i++) {
num += i; // 1+2+3+4
if(num >= X) { // i가 4일때, 10 >= 8 이므로 if문 실행됨
num -= i; // 10은 구하려는 숫자가 아니므로 다시 4를 빼줌
// num = 6(1+2+3)
int sequence = X - num; // sequence(순서) = 8-6 = 2
// 여기까지 생각했을 때
// X(8) = num(6) + sequence(2)
// i = 4
// 합이 5인 구간에서 2번째 순서, 5(i+1) - sequence(2) = 3
if(i%2==0) { // 짝수 구간, 8은 짝수구간이므로 if문 실행됨
// 짝수는 증가/감소 구간
bw.write(sequence+"/"+((i+1)-sequence)); // 2/3 출력
} else { // 홀수 구간
// 홀수는 감소/증가 구간
bw.write(((i+1)-sequence)+"/"+sequence);
}
break;
}
}
br.close();
bw.close();
}
}