1300번 - K번째 수
2차원 배열의 크기가 n라고 하면
2차원 배열에서 t번째 대각선상의 숫자의 갯수를 d[t]라고 하면
d[t] = t (t <= n)
d[t] = n - t (t > n)이 됩니다
.
n = 4, k = 8인 예를 들자면
d[1] = 1, d[2] = 2, d[3] = 3, d[4] = 4, d[5] = 3, d[6] = 2, d[7] = 1
이 되고
s[t] = sigma (i = 1 -> t) d[t]라고 하면
s[t]는 순서대로 1 3 6 10 13 15 16이 되죠.
그러면 k번쨰 수는 s[3] = 6과 s[4] = 10사이의 수이고
3 + 1번째 대각선의 수들을 정렬했을때 8 - s[3]번째 수가 답이 됩니다
따라서
n을 입력받은 후 s[t]배열을 미리 만들어두고
k를 입력받으면 s배열의 앞부터 k >= s[t]가 되는 첫 t에 대해
k -= s[t]해주면 이제 t번째 대각선에서 k-s[t]번째 숫자만 보면 된다는 아이디어로 풀었습니다.
(다만 t>n 이면 대각선에서 봐야하는 수들에 제약이 생깁니다. 2차원 배열의 i행 j열의 수들 중 i <= n, j <= n을 만족하는 수들만 카운트해야 합니다)
n을 1 4 5 6 1000 10000 100000으로 잡고 돌려도 의도한대로 답이 잘 나오는데
제출하면 틀렸다고 합니다.... 어디가 틀렸는지 사이드 케이스를 알 수 있을까요?
의도한 바가 틀려서 의도한 대로 나오면 틀리는 거 아닐까요
호고곡 뻘짓 하고 있었네요 ㅠ
감사합니다
댓글을 작성하려면 로그인해야 합니다.
vegatrash 4년 전
2차원 배열의 크기가 n라고 하면
2차원 배열에서 t번째 대각선상의 숫자의 갯수를 d[t]라고 하면
d[t] = t (t <= n)
d[t] = n - t (t > n)이 됩니다
.
n = 4, k = 8인 예를 들자면
d[1] = 1, d[2] = 2, d[3] = 3, d[4] = 4, d[5] = 3, d[6] = 2, d[7] = 1
이 되고
s[t] = sigma (i = 1 -> t) d[t]라고 하면
s[t]는 순서대로 1 3 6 10 13 15 16이 되죠.
그러면 k번쨰 수는 s[3] = 6과 s[4] = 10사이의 수이고
3 + 1번째 대각선의 수들을 정렬했을때 8 - s[3]번째 수가 답이 됩니다
.
따라서
n을 입력받은 후 s[t]배열을 미리 만들어두고
k를 입력받으면 s배열의 앞부터 k >= s[t]가 되는 첫 t에 대해
k -= s[t]해주면 이제 t번째 대각선에서 k-s[t]번째 숫자만 보면 된다는 아이디어로 풀었습니다.
(다만 t>n 이면 대각선에서 봐야하는 수들에 제약이 생깁니다. 2차원 배열의 i행 j열의 수들 중 i <= n, j <= n을 만족하는 수들만 카운트해야 합니다)
.
.
n을 1 4 5 6 1000 10000 100000으로 잡고 돌려도 의도한대로 답이 잘 나오는데
제출하면 틀렸다고 합니다.... 어디가 틀렸는지 사이드 케이스를 알 수 있을까요?