[오답노트] BOJ 1300: K번째 수 - JAVA

박철민·2022년 11월 28일
0

오답노트

목록 보기
1/14

K번째 수


난이도 : 골드 2
풀이 날짜 : 2022-11-28
출처 : https://www.acmicpc.net/problem/1300
참고 자료 : https://st-lab.tistory.com/281


처음에는 문제를 이 문제가 이분탐색이라는 점에서 숫자들을 정렬해야 하지 않을까 생각하였다.

그러나 최대 크기가 10^10이 int 표현 범위를 넘어가기 때문에 배열 선언이 불가능하다.

그렇다면 이것을 어떻게 할까?

밑에 참고로 한 글을 보고 아이디어를 받았다.


아이디어

이분탐색

3
7

다음과 같이 입력을 받았을 경우

1 2 3
2 4 6
3 6 9

와 같이 2차원 배열이 선언되고 이를 1차원 배열로 선언하면 다음과 같다.

1 2 2 3 3 4 6 6 9

이제 여기서 이분 탐색으로 7번째로 오는 숫자가 무엇인지 생각한다.

L = 1로 잡는다.
R = N * N 으로 9를 잡는다.

mid = (1 + 9) / 2 = 5;

그렇다면 이제 1차원 배열에서 mid가 어디에 있는지 확인을 한다.

이 확인을 하는 방법을 아래에서 서술

하지만 5는 표에 존재 하지 않기 때문에 4의 위치인 6을 출력해야 한다.

check(5) = 6

5의 위치가 6이기 때문에 다음과 같이 바뀝니다.

L = mid + 1 = 6
R = 9
mid = (6 + 9) / 2 = 7

7은 표에 존재 하지 않기 때문에 6의 위치인 8을 출력한다.

check(7) = 8


L = 6
R = mid - 1 = 6
mid = (6 + 6) / 2 = 6

이제 L과 R이 같기 때문에 6이전 것과 6 다음 것 사이에 7이 있음을 알 수 있다.

그러므로 B[7] = 6이 성립이 된다.


세는 방법

위에 말한 확인하는 함수로 매개변수 mid가 1차원 배열에 어디에 있는지를 확인하는 함수를 구현해보자!

이 아이디어는 참고 자료를 보고 이해를 했다.

내용을 간략히 한다면 숫자가 어디에 있는지는 그 숫자 보다 작거나 같은 숫자가 얼마나 많냐는 것이다.

1 2 3
2 4 6
3 6 9
다음과 같은 2차원 배열에서 4가 어디에 있는지를 알기 위해서 어떻게 해야 하는지를 생각해보자

각 왼쪽 렬 부터 4보다 작은 것이 몇개 있는지를 확인하면 된다.

1렬을 확인하면 4보다 작거나 같은 것이 다음과 같다.

1 2 3
2 4 6
3 6 9

2렬로 넘어간다면

1 2 3
2 4 6
3 6 9

3렬로 넘어간다면

1 2 3
2 4 6
3 6 9

다음과 4의 값은 6으로 구해진다.

이는 for문을 활용하여 mid보다 작은 숫자들이 각 렬마다 몇개인지 확인을 하는 방식으로 구하면 된다.

이 렬들을 자세히 보면
1의 배수, 2의 배수, 3의 배수로 그 갯수는 mid를 idx로 나눈 값이 된다.

그러나 행의 끝은 3(N)개이므로 최댓 값은 N이어야 한다.

정리하자면
for문을 이용해 각 렬 마다 각 idx 만큼 mid를 나눈 몫을 더해주는 것이다. 이 몫은 N을 넘어설 수 없다.

			long count = 0;
			
			for(int i=1; i<=N; i++) {
				count += Math.min(mid/i, N);
			}

이를 코드로 표현하면 다음과 같이 선언이 될 수 있다.


구현

위의 아이디어들을 차근 차근 코드로 짜보자

입력

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
        br.close();

이분 탐색

long l = 1;
long r = (long)N * N;

// l이 r과 같을 경우 멈춘다.
while(1 < r) {
	long mid = (l + r) / 2;
    long count = 0;
    
    // 각 렬마다 체크해보기
    for(int i=1; i<=N; i++){
   		// mid/i개 만큼 오지만 이는 N을 넘어서면 안 된다.
    	count += Math.min(mid/i, N);
    }
    
    // r = mid - 1이 아니다
    if(K <= count) {
    	r = mid;
    }
    
    else {
    	l= mid + 1;
    }
}
System.out.println(l);
profile
멘땅에 헤딩하는 사람

0개의 댓글