1300번 - K번째 수
S: ㄴ자를 시계로 90` 회전시킨 모양
ex) n = 3
1 2 3
2 4 6
3 6 9
첫번째 S
2
3
두번째 S
4 6
6
세번째 S
9
처음에 몇번째 S에 속해있는가를 구하기 위해 이분탐색을 사용해서 구하고
해당 값을 이용하여 답을 냈습니다.
몇 번째 S에 있는지를 이분탐색으로 찾을 수 없습니다. n = 3일 때에는 각 S에 들어있는 수가 겹치지 않아서 되는 것처럼 보이지만, 조금 더 키우면 수가 겹치게 됩니다.
어떤 수가 몇번째 S에 있는지를 찾는 것은 겹치겠지만
k번째 수가 몇번째 S에 있는지를 찾는 것은 겹치지 않지 않나요?
5
8
정답은 4인데 5가 출력됩니다.
수가 겹치므로 k번째 수도 겹칠 수밖에 없습니다.
이분탐색으로 찾을 수 있으려면 첫 번째 S에 k=1부터 k=a까지, 두 번째 S에 k=a+1부터 k=b까지, ..., 마지막 S에 k=z+1부터 k=N^2까지 순서대로 들어 있어야 하는데, n이 5 이상이면 이것이 성립하지 않습니다.
감사합니다.
제가 완전히 잘못 생각하고 있었네요
댓글을 작성하려면 로그인해야 합니다.
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에 속해있는가를 구하기 위해 이분탐색을 사용해서 구하고
해당 값을 이용하여 답을 냈습니다.