zxcv551133   5년 전

S: ㄴ자를 시계로 90` 회전시킨 모양

ex) n = 3

1 2 3

2 4 6

3 6 9


첫번째 S

1 2 3

2

3

두번째 S

4 6

6

세번째 S

9

처음에 몇번째 S에 속해있는가를 구하기 위해 이분탐색을 사용해서 구하고

해당 값을 이용하여 답을 냈습니다.

jh05013   5년 전

몇 번째 S에 있는지를 이분탐색으로 찾을 수 없습니다. n = 3일 때에는 각 S에 들어있는 수가 겹치지 않아서 되는 것처럼 보이지만, 조금 더 키우면 수가 겹치게 됩니다.

zxcv551133   5년 전

어떤 수가 몇번째 S에 있는지를 찾는 것은 겹치겠지만

k번째 수가 몇번째 S에 있는지를 찾는 것은 겹치지 않지 않나요?

djm03178   5년 전

5

8

정답은 4인데 5가 출력됩니다.

jh05013   5년 전

수가 겹치므로 k번째 수도 겹칠 수밖에 없습니다.

이분탐색으로 찾을 수 있으려면 첫 번째 S에 k=1부터 k=a까지, 두 번째 S에 k=a+1부터 k=b까지, ..., 마지막 S에 k=z+1부터 k=N^2까지 순서대로 들어 있어야 하는데, n이 5 이상이면 이것이 성립하지 않습니다.

zxcv551133   5년 전

감사합니다. 

zxcv551133   5년 전

제가 완전히 잘못 생각하고 있었네요

댓글을 작성하려면 로그인해야 합니다.