Rush : Dlbo군의 Matrix Solution

네, 논란이 많았죠, Matrix

류엔트군은 술마시고 코딩해서 기억이 안난다고 하질 않나

Dlbo군은 류엔트군의 풀이와 99% 같은 코드를 올리고는

미리 풀긴 했는데 정리를 못한 상태에서 류엔트군의 AC가 올라오니까 그걸 보고 자기 풀이의 군더더기를 뺐다고 하질 않나

(사실 물증이 없어서 아직도 1%정도 의심은 가지만, 여기선 그걸 추궁하는게 아니니까 그냥 믿고 넘어갑니다)

그것 때문에 제가 뭔가 납득이 갈 만한 풀이를 올려달라고 했고,

얼마 전에 Dlbo군이 솔루션을 올려주었지요

솔루션을 읽고나서 알고리즘을 직접 적용해보니 아주 정확히 답이 떨어집니다

알고리즘의 목적( M번째 작은 값을 K라 가정하고, K보다 작은 값을 가지는 행렬상의 원소의 개수를 counting하는 것 )도 꽤나 깔끔하고, 합리적이지요

결론부터 먼저 말하자면,

저 코드로 아주 정확히 답을 찾아낼 수 있으니까

Dlbo군의 솔루션이 이해가 되는 분들은 과감히 '뒤로가기'를 눌러주셔도 됩니다

----------------------------------------

이제 Dlbo군의 솔루션이 뭔소린고 하는 분들만 이 아래를 보시면 됩니다

문제가 되는 부분은 Dlbo군의 설명부분인데..

일단,

솔루션에서의 x와 코드상의 x가 다른 의미를 가지고 있는 상태에서 표기가 중복되므로 의미의 모호함을 가질 수 있습니다

솔루션의 본문을 잘 읽으면 그것에 대해 언급을 했지만, 처음 솔루션을 보는 사람들에게는 난감할 수 있지요

어차피 AC받은거 또 제출할 일은 없으니 코드의 일부를 솔루션에 맞춰서 수정했어도 좋았을거라는 생각은 들지만.. 뭐 그건 상관없습니다

하나 더,

행에 관한 변수 i를 x로 치환해놓고,

j에 대해 언급할 때 '열'이 아닌 '줄'이라고 표현을 했는데, 이것 역시 처음 솔루션을 보는 사람들에게 매우 난감할 수 있습니다

그리고 자기 코드에 대해 잘 설명하다가 중간중간 류엔트의 코드와의 차이점을 언급하는데,

이건 읽는 사람의 몰입도에 방해를 줄 수 있으니 참고하세요 -_-;

또,

외부 while문이 min < max인 동안 돌도록 설계된 것이 류엔트군의 실수라고 했는데,

그러는 너는 왜 while문이 min < max인 동안 돌도록 해놨나여 ㅇㅇ?

그리고

cal_1( 이하 α; 알파라고 하겠습니다 )과 cal_2( 이하 β; 베타라고 하겠습니다 )가 실수값이 나오는 것에 대해 좀 걱정을 해놨던데

K가 무슨 값을 갖든지 알파와 베타가 정수값이 안나오는 열이 존재합니다

알고리즘을 돌리면서 확인해보니 알파와 베타는 실수값이 나와도 상관없습니다 -_-;

알고리즘을 몇번 돌려본 것을 바탕으로 추측해보건대, 알파는 항상 음수가 나옵니다

베타는 음수가 나올 때도 있고 양수가 나올 때도 있는데,

베타가 음수일 때는 고려하지 않으니 패스하고, 베타가 양수가 되면 알파·베타 모두 integer형에 쑤셔넣듯이 truncate하면 됩니다

그리고 예전에 Dlbo군이 코드에 쓰인 j는 사실 j가 아니고 i다 라는 말을 했었는데

솔루션을 읽어보니 그건 그냥 j가 맞습니다, 패스

아 마지막으로,

Dlbo군은 변수 det가 음수가 될 때의 경우는 전혀 생각하지 않은 듯 한데 -_-

우리의 자비로운 sqrt함수는 input으로 음수가 들어오니 output으로 0을 반환해주더군요

하지만 det에 대한 처리는 류엔트군의 코드가 맞으니 참고하세요 -_-;

----------------------------------------

이제 태클은 대충 됐고,

제가 예전에 Solving Process에 올렸던 1/5000 사이즈의 문제에 대해서 이 알고리즘을 적용해보겠습니다

i행 j열의 원소의 값을 나타내는 식 a_ij는 i² + 100000i + j² - 100000j + ij 인데,

행렬의 최대 사이즈가 될 수 있는 50000에 대해 다루기가 힘들기 때문에,

크기를 1/5000로 줄여서 최대 사이즈를 10으로 고정합니다

이때 a_ij를 보면

작은 수로 취급될 법한 i, j에 비해 큰 수 100000이 있는데,

최대 사이즈 50000을 10으로 줄였으니 위의 100000은 20으로 줄여보도록 합시다

그러면 우리는 a_ij = i² + 20i + j² - 20j + ij 를 얻을 수 있고,

N을 10( 최대 사이즈 )으로 고정하면 다음과 같은 행렬을 얻을 수 있습니다

위에서 붉은색으로 강조된 부분은 각 행에서 최소값을 가지는 원소를 표시해놓은 것입니다만,

파일을 재활용한 것이므로 이 풀이에서는 별로 필요 없습니다

이렇게 5만과 10만에 대해 각각 1/5000을 적용한 위의 행렬은

기존 문제( PKU 3685 )에서 제시하는 최대 5만×5만짜리 행렬이 갖는 성질을 그대로 가집니다

이제 M을 적당히 하나 잡아서, M번째 작은 값을 솔루션의 알고리즘을 통해 위의 행렬에서 찾아보도록 합시다

pku_3685_mini.xlsx

( 엑셀 2007에서 작성한 문서입니다 )

사용자가 수동으로 바꿔줘야하는 값은 max, min, M 세가지 뿐이니

max의 초기값은 400으로, min의 초기값은 -400으로, M은 1 이상 100 이하로 적당히 잡고

소스의 아랫부분에 있는 if( sum < M ) … else … 부분의 statement에 대해서만 수동으로 바꿔주면 됩니다

그러다보면 언젠가 max와 min이 같아지는 때가 나오는데,

그 때가 되면 더이상 while문을 돌지 않으므로 그게 답이 됩니다

- End -