blutics   5년 전

반례를 찾기가 힘드네요. 테스트 케이스 만들어서 돌려봐도 딱히 나오지는 않는데.....

hello70825   5년 전

invalid grille이 나와야되는데

wronngswaareadat 라고 출력됩니다.

blutics   5년 전

이게 왜 invalid인거죠?? 적어도 좌측 상단 4개만 있어도 invalid grille은 아니지 않은가요??

처음 주어지는 grille과 회전3번해서 생기는 값들까지 총 4개의 grille에서 나오는 수들이 전체를 커버해주면 되는거 아닌가요??

제가 뭔가 잘 못 이해하고 있는건가요??

hello70825   5년 전

입력의 마지막 줄은 암호화할때 나온 텍스트를 입력하는 것입니다.

본문에 나온 예제1 그림이 잘 설명해주고 있습니다.

따라서 위의 그릴이 정답을 받으려면

4

...X

..XX

.XXX

XXXX

wrongaronswerwredatnaaada

로 입력되어야합니다.

하지만 이러면 '암호화된 문장의 글자수는 항상 n의 제곱이다'라고 적혀있는 입력 조건에 위배되기 때문에 문제 조건에 맞지 않는 그릴이 됩니다.

hello70825   5년 전

생각해보니 저러면 제가 올린 반례가 틀리게 되는 것이군요.

메세지가

wron

ngsw

aare

adat

이고, 그릴이

...X

..XX

.XXX

XXXX

일 때 입력의 마지막 줄은

wrongaronswerwredatnaaada

로 입력해야 한다고 생각하시면 됩니다.

blutics   5년 전

아직은 뭔가 반례가 안보인다는 말씀이시죠??

hello70825   5년 전

아뇨 반례가 맞습니다

제 머릿속에서는 이해가 가는 내용인데 남한테 설명해주자니 전달하기가 힘드네요 ㅠㅠ

일단 생각의 흐름대로 적어보겠습니다.

결론부터 말하자면 ' 암호화된 문장의 글자 수는 항상 n의 제곱이다 ' 라는 내용 때문에 .의 개수가 (n**2)//4 일 때만 문제에 만족 할 수 있는 그릴이 나옵니다.

메세지 위에 그릴을 놓고 알파벳을 적고, 90도 회전해서 본 알파벳을 또 적고, 또 회전해서 적고, 또 회전해서 적고 해서 총 4번을 보고 적은 알파벳을 그릴의 모양을 입력한 후 다음 줄에 입력하는 방식인데요.

그릴에 나온 .의 수는 똑같은데(만약 .의 개수를 x개,n의 입력을 N이라고 쳐봅시다) 총 4번을 보고 암호를 입력하니 4*x개의 알파벳이 나오는데요.

이때 입력 조건에서 '암호화된 문장의 글자 수는 항상 n의 제곱이다' 라는 내용 때문에 N**2=4*x 라는 식이 만족해야 해서 .의 개수가 (n**2)//4 일 때만 문제에 만족 할 수 있는 그릴이 나옵니다.

위에 나온 wronganswerdataa를 다시 예시로 들어봅시다.

문제에 ' 암호화된 문장의 글자수는 항상 n의 제곱이다' 라는 내용이 없다고 하면, 입력의 마지막 줄을 'wrongaronswewredatnaaada' 라고 입력 했을 경우 blutics님의 코딩대로 wronngswaareadat 입니다.

하지만 'wrongaronswewredatnaaada'은 16개의 글자가 아닌 24개의 글자로 이루어져 있으므로 그릴이 문제 조건에 만족하지 못하는 그릴이라고 할 수 있습니다.


blutics   5년 전

그런데 본문에 보면 " The message is encrypted by writing down the letters that appear in the holes, row by row, then rotating the grille 90 degrees clockwise, writing the new letters that appear, and repeating this process two more times."에서 새로운 단어가 나올때 적어준다고 했으므로 n**2%4가 0이 아닌 케이스에 대해서도 풀리는거 아닌가요??

hello70825   5년 전

새로운 글자들이라는 것이 그릴을 돌려서 나오는 글자들을 보고, 새로운 글자들이라 말하고 있다고 생각합니다.

blutics님 말대로 하자면 writing the new letters that appear 라고 하기보다는 writing the new letters that had not been seen message on the holes가 맞지 않을까요?


blutics   5년 전

그러면 애초에 그릴에서 구멍의 개수가 정확히 전체의 1/4인 경우만 되어야되는거겠군요??

n이 홀수인 케이스도 될 수가 없구요. 흠.....

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