[파이썬] 1300 K번째 수 feat.. 넘모 어려워

 

일단 고질병인 문제 잘 안 읽기를 넘어선

 

이해가 안 가는 문제였다

 

첫 줄부터 막혔다

 

n*n의 배열 A를 만들었다 >> ?? 

 

처음에는 n*n이라길래 아 그럼 제곱수짜리 1차원 배열인 건가 했다

 

근데 그 다음에 나오는 a[i], a[j]를 보고

 

아 ;;; 열받네 뭔 소리야 하면서 끈 기억이 난다

 

 

그리고 오늘 이해갈 것 같아서 다시 봤다

 

n*n이니 .. 그럼 a [0][0]부터 a [n][n]이라는 뜻이겠구나라고 다시 이해했다

 

아마 술에 취한 상태로 봐서 그런 듯하다

 

그럼 다음 줄을 이해해야 한다 

 

이 수를 일차원 배열 B에 넣으면 B의 크기는 N*N이다 

 

그렇지.. N값이 3이면 

 

1 2 3 2 4 6 3 6 9 = len(B) = 9 

 

여기까진 이해했다

 

오름차순 >> 1 2 2 3 3 4 6 6 9

 

여기서 답은 b[k]를 구하라 한다..

 

머리가 아파왔다

 

 

1차 힌트로 이분 탐색이 있는 걸 알고 있다

 

그래서 일단 무작정 변수 2개와 이분 탐색 문장을 만들었다

arysize=int(input()) mx = int(input()) start, end = 1, while start <= end:     mid = (start+end)//2     if  >=mx:         end = mid-1     else:         start = mid +1 print(ans)

이제 값을 찾아야 한다

 

1. 초기 end값

 - 이건 어렵지 않았다

 

잘 보면 1,2 까지는 같지만 3부터는 무조건 mx 값보다 작다 

 

고로 mx를 그냥 end값으로 둔다

 

2. mid값

 

여기서 막혔다

 

한 시간 정도 머리를 싸맨 것 같다

 

결국 다른 분들의 답을 보기로 했다

 

근데 하나같이 이해가 안 갔다

 

다들

 

tmp += min(mid//i, arysize)

 

이런 식으로 tmp값을 모아서

mx값보다 크면 ! 이런 식으로 ans를 더해나갔다 

 

정말 이해가 안 갔다

 

그래서 또 한 시간을 답변 풀이를 헤맸다

 

그러다가 어찌어찌 이해한 풀이로 해설을 적어보려 한다

 

 

예시를 약간 바꿔 arysize 값을 4, mx를 10으로 바꿔보자

 

 

 

우리가 찾고 싶은 건 b[10]값이다 

차례대로 했을 때 10 값은

 

6이다

 

그럼 6일 때 답이 10이라는 건데

 

10은 각 행의 6보다 작은 숫자의 표에 있는 총 칸의 합이다

 

감이 오는가?

 

뭔가 감이 안 오는데 안 올 것이다 내가 실제로 그랬다

 

좀 더 고민해보자 

 

우리는 숫자에 대한 규칙을 찾는 게 아닌

 

표 자체에서의 규칙을 찾아야 한다

 

그럼 b[10]을 찾고 싶은데

 

6 이하의 수를 찾는 것이 아닌

 

5 이하의 수를 센다고 생각해보자 

 

 

그렇다 결국 b[7]에서 멈출 것이다

 

그럼 우리가 필요한 mid값의 조건은 찾았다

 

p 줄의 최댓값이 되는 수 = mid라고 생각하면 된다

 

그런데 여기서 고민하면 또 한두 시간 헤맨다

 

아까 말했듯 표 자체의 식을 찾아야 한다 

 

표를 잘 보면 하나같이 min(6(mid)에서 i혹은 p를 나눈 수, arysize)인 것을 볼 수 있다

 

그럼 mid가 6일 때

 

첫 행에서의 mid가 6일 때의 개수는 min(6/1, 4) = 4

두 번째 행에서의 개수는 min(6/2, 4) = 3

.

.

 

4+3+2+1 = 10

 

아까 본 6일 때의 10이 나왔다 

 

반대로 5일 때는 

 

첫행에서의 mid가 5일 때 개수는 min(5/1,4) = 4

두 번째 행에서의 개수는 min(5/2, 4) = 2

.

.

4+2+1+1 = 7

 

 

풀이는 다 나왔다 이제 코드로 옮기기만 하면 된다

 

 

arysize=int(input()) mx = int(input()) start, end = 1, mx while start <= end:     mid = (start+end)//2     tmp = 0     for i in range(1, arysize+1):         tmp += min(mid//i, arysize)         if tmp >=mx:         ans = mid         end = mid-1     else:         start = mid +1 print(ans)

tmp값을 만들어서 mid//i 값을 다 더해준다 (각 행의 개수)

 

그리고 tmp값이 mx 보다 적다면 mid값이 더 커야 하므로

 

mid값을 우측으로 옮기기 위해

 

start에 mid+1을 해서 while문을 다시 돌린다

 

반대로 크거나 같을 경우 mid값이 더 적을 가능성이 있기 때문에 

 

mid값의 왼쪽을 보기 위해 end값을 mid-1 값으로 주고 while문을 돌린다

 

 

 

-

 

사실 이렇게 풀긴 했는데

 

1000% 한 달 후에 다시 풀라 하면 헤맬 것 같다 

 

별표 찍어놓고 한 달 후에 다시 도전해봐야겠다