[백준(BOJ)] 1300번 : K번째 수 - PYTHON[파이썬]

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

1300번: K번째 수

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색
• 매개 변수 탐색

 

---

 

⊙ 문제 접근 과정

 

우선 문제를 보고, 무지성으로 N에 3을 넣은 2차원 배열 A를 만들어줬다.

그리고 바로 i와 j를 곱한 값을 A[i][j]에 넣어 2차원 배열 A를 완성시켰다.

 

 

 

2차원 배열 A의 값들을 1차원 배열 B에 넣고 정렬하여 B[k-1]를 출력해주었다.

그랬더니 출력 값이 아주 예쁘게 나왔다.

 

❌

import sys

input = sys.stdin.readline

N = int(input())
k = int(input())
A = [[] for _ in range(N)]

for i in range(N):
    for j in range(N):
        A[i].append((i+1)*(j+1))

B = sum(A, list())

B.sort()

print(B[k-1])

제 코드랑 똑같으신 분 있나요? ㅋㅋㅋㅋ..

 

결과는 메모리 초과

 

역시 이렇게 해결되면 골드 2가 아니다.

 

---

 

2차 접근

그다음은 알고리즘 분류를 쳐다봤다.

이분 탐색은 알겠는데 오잉? 매개 변수 탐색?

 

그래서 공부해봤다.

 

🧐 매개 변수 탐색

이거 하나만 기억하자.

 

이진 탐색은 찾고자 하는 값을 찾으면 바로 종료한다.

하지만 매개 변수 탐색은 찾고자 하는 값을 찾아도 탐색할 배열이 남아있다면 끝까지 탐색한다.

 

WHY?

최댓값을 찾기 위해서

 

 

---

 

1. 이분 탐색 기초적인 토대 작업

start, end = 0, k

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

 

 

2. 개수를 전부 모은 변수 생성 (🔥)

    cnt = 0

    for i in range(1, N+1):
        cnt += min(mid//i, N)

 

개수를 찾는 문제이니 개수 관련 변수를 생성해주었다.

위 식은 다음과 같다.

 

예를 들어 3X3 배열이 있다.

1 이하의 수 = 1개

2 이하의 수 = 3개

3 이하의 수 = 5개

4 이하의 수 = 6개

5 이하의 수 = 6개

6 이하의 수 = 8개

7 이하의 수 = 8개

8 이하의 수 = 8개

9 이하의 수 = 9개

 

개수 관련 변수 cnt 생성!

 

그리고 마지막으로 이분 탐색으로 찾고자 하는 값을 찾아가면 된다.

 

---

 

⊙ 문제 풀이

 

import sys

input = sys.stdin.readline

N = int(input())
k = int(input())

start, end = 0, k

while start <= end:
    mid = (start+end)//2
    cnt = 0

    for i in range(1, N+1):
        cnt += min(mid//i, N)

    if cnt >= k:
        answer = mid
        end = mid - 1
    else:
        start = mid + 1

print(answer)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

오랜만에 알고리즘

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!