Java 백준 문제풀이 (57) 1300 _ K번째 수

 

어렵다.

이진 탐색 문제는 원래 다 이렇게 어려운 걸까?

예전에 풀었던 문제인데 나중에 반드시 다시 풀어보겠다고 생각했고 그게 오늘이다.

오늘도 글 쓰면서 실시간으로 도전한다.

 

우선 문제를 읽고 조건을 정리해보자.

 

 

 

 

        // A = new int[N][N]
        // A[i][j] = i*j
        // 1차원 배열로 변경? B = new int[N*N];
 
        // 예제 입력값 (3, 7)의 경우
        // 1 2 3
        // 2 4 6
        // 3 6 9
        // B[7] = 6
 
       // 문제를 풀기 위한 조건들
        // 1. B[x]는 x보다 작거나 같다.
        // 2. B[x]에서 x는 B[x]보다 작거나 같은 수의 개수와 같다.
        // 3. B[x]에서 x는 Math.min(B[x]를 1 ~ N까지수로 나눈 값, N)의 합과 같다.
        // ( 3 + 3 + 1 )

이 문제의 난관은 2개다.

첫 번째는 이진 탐색으로 풀어야 한다는 사실과 그 방법을 추론하는 것.

두 번째는 Lower Bound.

Lower Bound는 모르면 따로 찾아보자.

 

난 둘 다 스스로 못해서 해설 보고 배웠었다.

ㅋㅋㅎ

 

우선 문제를 보고 도저히 알 수 없고, 예제가 간단하게 주어진 경우에는 예제를 적어보고 그 안에서 규칙성을 찾아내는 게 제일 효율적이다.

 

예제에서 입력값이 (3, 7)일 때 정답은 6이라고 한다.

입력값이 3인 경우는 아래와 같다.

 

1 2 3

2 4 6

3 6 9

 

엥 ? 구구단 표가 완성이 될 것 같은 행렬이다.

그리고 이걸 1차원 배열로 옮기면 이런 형태가 된다.

 

1 2 2 3 3 4 6 6 9

 

따라서 7번째 값은 6이 나오는데, 우리는 여기서 몇 가지를 알 수 있다.

 

1. B[x]는 반드시 x보다 작거나 같다.

숫자가 더 늘어나도 마찬가지다.

 

2. B[x]에서 x (몇 번째 수인지)는 B[x]보다 작거나 같다.

 

3. B[x]에서 x는

int answer = 0;

for (int i=0; i<N; i++) {

answer += Math.min(x/N, N)

}

과 같다.

 

즉, 임의 수를 놓고 answer가 m과 같아지는 경우를 찾아야하며

비교하는 범위는 최대 x와 같다는 것이다.

 

위 조건들을 전제로 문제를 풀어보자.

바로 야매 수도코드를 작성해보았다.

 

 

 

 

 

public class Main {
    public static void main(String[] args) {
        // A = new int[N][N]
        // A[i][j] = i*j
        // 1차원 배열로 변경? B = new int[N*N];
 
        // 예제 입력값 (3, 7)의 경우
        // 1 2 3
        // 2 4 6
        // 3 6 9
        // B[7] = 6
 
        // 문제를 풀기 위해 유추해내야 하는 조건들
        // 1. B[x]는 x보다 작거나 같다.
        // 2. B[x]에서 x는 B[x]보다 작거나 같은 수의 개수와 같다.
        // 3. B[x]에서 x는 Math.min(B[x]를 1 ~ N까지수로 나눈 값, N)의 합과 같다.
        // ( 3 + 3 + 1 )
 
        // 배열 크기 N 입력 받기.
        // 구해야하는 수 K 입력 받기.
 
        // 바로 이진 탐색(N, K)
    }
 
    // 이진탐색 (배열 크기 N, 구해야하는 자리수 K)
    // l = 1 (인덱스가 1부터 시작한다.)
    // r = K (구해야하는 수 B[K]는 K보다 작거나 같다.)
 
    // while (l<=r)
    // m = (l+r) /2;
    // 카운트 변수
    //
    // 반복문 ( N만큼 )
    // {
    // count += Math.min(m / N, N)
    // }
    //
    // 만약 ( count가 m보다 크거나 같을 경우 ) l = m+1;
    // 아니라면 r = m-1;
    //
    // 출력 l
}

 

방금 작성한 거라서 나도 맞는지 틀렸는지 모른다.

지금 풀어보고 오겠다.

 

 

 

전체적으로 맞았는데 중간에 말도 안되는 이상한 주석을 작성해놨다.

이진 탐색 안에..

 

문제를 풀기 위한 조건들을 이해했다면 어느 부분이 문제인지 찾아낼 수 있을 것이다.

 

근데 나만 이렇게 어려운 거 아니겠지?

유형 조금만 다르게 나와도 풀 자신 없음 ㅎㅎ

 

정답은 아래에.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // A = new int[N][N]
        // A[i][j] = i*j
        // 1차원 배열로 변경? B = new int[N*N];
 
        // 예제 입력값 (3, 7)의 경우
        // 1 2 3
        // 2 4 6
        // 3 6 9
        // B[7] = 6
 
        // 문제를 풀기 위해 유추해내야 하는 조건들
        // 1. B[x]는 x보다 작거나 같다.
        // 2. B[x]에서 x는 B[x]보다 작거나 같은 수의 개수와 같다.
        // 3. B[x]에서 x는 Math.min(B[x]를 1 ~ N까지수로 나눈 값, N)의 합과 같다.
        // ( 3 + 3 + 1 )
 
        // 배열 크기 N 입력 받기.
        int N = Integer.parseInt(br.readLine());
        // 구해야하는 수 K 입력 받기.
        int K = Integer.parseInt(br.readLine());
 
        // 바로 이진 탐색(N, K)
        binary_search(N, K);
    }
 
    // 이진탐색 (배열 크기 N, 구해야하는 자리수 K)
    public static void binary_search(int n, int k) {
        // l = 1 (인덱스가 1부터 시작한다.)
        int l = 1;
        // r = K (구해야하는 수 B[K]는 K보다 작거나 같다.)
        int r = k;
        while (l<=r) {
            // while (l<=r)
            // m = (l+r) /2;
            int m = (l + r) / 2;
            int count = 0;
            // 카운트 변수
            // 반복문 ( N만큼 )
            for (int i = 1; i <= n; i++) {
                // count += Math.min(m / N, N)
                count += Math.min(m / i, n);
            }
            //
            // 만약 ( count가 m보다 크거나 같을 경우 ) l = m+1;
            if (count < k) l = m+1;
                // 아니라면 r = m-1;
            else r = m-1;
            //
        }
            // 출력 l
        System.out.println(l);
        }
    }

 

주석은 무시하자