[Java] 백준 1193번

Input-1
1
Output-1
1/1

Input-2
2
Output-2
1/2

Input-3
5
Output-3
2/2

Input-4
9
Output-4
3/2

문제 풀이

먼저 배열의 행들을 대각선으로 바라보고 접근하면 더욱 이해가 빠를 것이다.
본인은 문제를 이해하는 데도 상당히 오래 걸렸다..

입력받은 수를 X라 하면 특정 패턴을 통해 X번째의 분수값을 찾아야 한다.

• X가 몇번째 행인지(몇번째 대각선 행) 찾는다.
• X의 행을 알았다면, 행 내에서 몇번째 원소인지 찾는다.
• X가 짝수행인지 홀수행인지 구분하여 분수값을 찾는다.

어느 행에 존재하는가?

먼저 X가 몇번째 대각선 행에 존재하는 값인지를 알아보자.
X의 범위를 검증해줄 cnt변수와 몇번째 행일지를 저장할 row 변수를 선언 및 초기화한다.
1번째 행부터 반복하며 찾아야 하니 row는 1로 초기화한다.

int row = 1; // 몇번째 행인지
int cnt = 0; // X의 범위를 찾을 변수

아래 식의 값이 X보다 클 때의 row(행)값을 통해 X가 몇번째 행인지 알 수 있다.

• 행 * (행 + 1) / 2

구체적으로는 while문에서의 X>cnt 조건이 거짓이 될 때 row값을 알고 있으면 된다.
예를들어 X가 5라고 하자. row는 1부터 순차적으로 증가한다.

cnt = 1*(1+1)/2 = 1
cnt = 2*(2+1)/2 = 3
cnt = 3*(3+1)/2 = 6

위와 같이 cnt가 6이되면 X보다 크므로 반복문을 탈출하게되고
그때의 row 값을 통해 X가 5라면 3번째 행에 존재하는 분수값임을 알 수 있다.

이렇게 구상해본 로직을 코드로 작성해보면 아래와 같다.

while(X>cnt) { // 행의 개수 증가시키며 X의 범위를 찾는다.
    row++; 
    cnt = row*(row+1)/2;
}

몇번째 원소인가?

다음으로 X가 어느 행의 값인지 알았으니 해당 행에서 몇번째 원소에 존재하는지 알아보자.

해당 행에서의 원소순서를 찾아 저장할 idx 변수를 선언하고 초기화한다.

int idx = 0; // 해당 행에서의 원소순서

아래 식을 통해 해당 행에서의 몇번째 원소인지 알 수 있다.

• X(주어진 수) - (행-1) * 행 / 2

예를 들어 X가 5일 때는 3번째 행임을 알고 있다.
해당 식에 값을 대입해보자.

// X=5
idx = 5-(3-1)*3/2 = 2

X가 5라면 3번째 행의 2번째 원소임을 알게되었다.
idx를 구하는 식도 코드로 작성해보자.

idx = X - (row-1)*row/2;

분수값을 찾아내자

자 앞에서 X가 어느 행의 몇번째 원소인지 찾아냈다.
이제 짝수행인지 홀수행인지 구분하여 분자와 분모값을 구해보자.

분수배열을 기준으로 홀수행일 경우 우측상단으로 진행되고
짝수행일 경우 좌측하단으로 진행되는데 이때 홀수행과 짝수행일 때의 분자, 분모값이 다르다.

• 홀수행이면 분자는 감소, 분모는 증가
• 짝수행이면 분자는 증가, 분모는 감소

분자값을 top, 분모값을 bot라는 변수로 선언하고 초기화하자.

int top = 0; // 분자
int bot = 0; // 분모

먼저 홀수행일 때를 보자.
top(분자)가 행값에서부터 -1씩 감소하는 값으로 이루어진다.
아래 식으로 분자값을 찾을 수 있고 분모값은 현재 idx(원소순서) 값과 같다.

• top(분자) = row(행) - idx(원소순서) + 1
• bot(분모) = idx(원소순서)

// 홀수행일 경우
top = row-idx+1;
bot = idx;

그리고 짝수행일 때는 홀수행과 반대이므로 분자와 분모를 반대로 대입해서 풀면 된다.

• top(분자) = idx(원소순서)
• bot(분모) = row(행) - idx(원소순서) + 1

// 짝수행일 경우
top = idx;
bot = row-idx+1;

예를 들어 X=4 라면 3번쨰의 행의 1번째 원소이다. 값을 대입해보자.
X=4 일 때 3번째 행의 1번째 원소인 3/1를 찾을 수 있다.

• top = 3-1+1 = 3
• bot = 1

그렇다면 홀수행과 짝수행을 검증하여 분자와 분모값을 찾는 코드를 작성해보자.

if (row%2==1) { // 홀수행
    top = row-idx+1;
    bot = idx;
    
}
else { // 짝수행
    top = idx;
    bot = row-idx+1;
}

작성코드

import java.io.*;

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 row = 1;
        int cnt = 0;
        int idx = 0;
        int top = 0;
        int bot = 0;
        
        if(X == 1) {
            top = 1; 
            bot = 1;
        }
        else {
            while(X>cnt) {
                row++; 
                cnt = row * (row+1) / 2;
            }
            idx = X - (row-1)*row/2;
            if (row%2==1) {
                bot = idx;
                top = row-idx+1;
            }
            else {
                bot = row-idx+1;
                top = idx;
            }
        }

        bw.write(top + "/" + bot);
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 백준의 기본수학 단계의 문제를 푸는데 브론즈 1 문제인데도 기초 수학 지식이 부족해서인지 처음에 문제를 읽는데 이해도 잘 안되고, 패턴 파악에 굉장히 많은 시간을 보내고 있다.ㅠ
• 문제의 내용을 보고 충분히 어려가지 패턴을 생각해내어 정답에 근접할 수 있는 로직 자체를 구상하는 시간을 줄이는 것이 중요한 것 같다.