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으로 잡고 돌려도 의도한대로 답이 잘 나오는데

제출하면 틀렸다고 합니다.... 어디가 틀렸는지 사이드 케이스를 알 수 있을까요?

sait2000   4년 전

의도한 바가 틀려서 의도한 대로 나오면 틀리는 거 아닐까요

vegatrash   4년 전

호고곡 뻘짓 하고 있었네요 ㅠ

감사합니다

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