[백준] 1300번 K번째 수 _ Python

https://www.acmicpc.net/problem/1300

[초기 접근 방법(X)]

1. N^2의 [i][j] 값을 모두 lst에 넣으려면 시간복잡도가 이미 O(N^2)으로 시간초과이다.

2. 그러면? 시간복잡도를 줄일 수 있는 방법은, 처음부터 [i][j] 값을 lst에 넣지 않는 것

3. 그런 [i][j] 값을 전부 넣지않고, 어떤 값을 lst에 넣어야 하는가?

 

에서 시작했다.

 

대각선을 기준으로 중앙값이 가장 크므로,

이분탐색을 하여 몇번째 대각선인지 찾고 남은 인덱스만큼 이동탐색하면 K번째 수를 찾으려고 했다.

 

 

 

[생각]

위 방식대로 로직을 짜고 풀었지만 결과는 "틀렸습니다"

저 로직을 생각하는데도 시간을 많이 썼던 문제라서, 미련없이 정답 코드를 참고했다...

일단 K번째 수는 '1행의 원소들'이 존재하므로 무조건 K보다 작다.

따라서 binary search의 범위는 1~K로 좁혀진다.

그리고 위 범위에 해당하는 수 mid를 정하고, 각 행의 mid보다 작은 수를 카운트한다.

카운트한 수가 문제에서 원하는 K에 근접하도록 이분탐색을 계속 진행해주고, 그 값을 출력하면 되는 문제이다.

 

 

 

[초기 코드]

# 맞는지 보자..
# moveIdx와 reverse 개념 수정 (자기자신 포함 안 했었음)
# lst[idx] == K 수정

N = int(input()) # 배열의 크기
K = int(input()) # 오름차순 정렬했을 때, k번째 인덱스

lst = [0] # 경계값 리스트
num = 0
# 앞 경계
for i in range(1, N+1):
    num += i
    lst.append(num)

# 뒤 경계
for i in range(1, N):
    num += (N-i)
    lst.append(num)


def search(start, end):
    while start < end:
        mid = (start + end) // 2

        if lst[mid] < K: # K, 경계값 lower_bound 탐색
            start = mid + 1

        else:
            end = mid

    # lower_bound(K 이상값) 반환
    # lst[end] : K 다음 경계값
    return end

idx = search(0, len(lst)-1) # 시작, 끝 인덱스
if lst[idx] == K:
    row = 1
    col = 1

    judge = True
    for _ in range(idx-1):
        if judge:
            col += 1
            judge = False

        else:
            row += 1
            judge = True

    print(row*col)

else:
    moveIdx = K - lst[idx-1] - 1

    # 대각선 경계를 기준으로 아래
    if lst[N] < K:
        row = N
        col = idx-N+1

    # 위
    else:
        row = idx
        col = 1

    # 왔다갔다 탐색한다.
    reverse = True
    for _ in range(moveIdx):
        if reverse:
            row, col = col, row
            reverse = False

        else:
            row += 1
            col -= 1
            reverse = True

    print(row * col)

 

 

[참고해서 작성한 코드]

# 풀이 시간 : 2시간 + 1시간
# 시간복잡도 : O(Nlog(K))
# 공간복잡도 : O(1)
# 참고 : https://kbw1101.tistory.com/29

# 이 문제의 핵심은, lst[K]의 정의이다.
    # lst[K] = x 일 때,
    # x보다 작거나 같은 값이 K개 있다는 의미

    # 따라서 범위(1~K) 내에서 mid 값보다 작거나 같은 값이 K개가 되는 최적값을 찾아 반환한다.

N = int(input())
K = int(input())

def search(start, end):
    while start < end:
        mid = (start + end) // 2

        # mid보다 작거나 같은 i*j값 찾기
        cnt = 0
        for i in range(1, N + 1):
            # 각 행의 col 값은 행(i)의 배수이므로,
                # 작은 값을 찾을 때 //i 를 해주면 된다.
            cnt += min(mid // i, N)

        if cnt < K:
            start = mid + 1

        else:
            end = mid

    return end


# end가 'K'인 이유
    # B[k]의 값은 k보다 작거나 같기 때문이다.
    # 1행의 값 때문에 '1~n'은 보장된다.
print(search(1, K))