헉... 생각도 못한 케이스네요. 앗....
어떻게 접근하신 건지는 코드 분석을 해 보겠습니다.
저 경우는 2 x 5짜리 가희가 4 x 5짜리 베개 위에서 자고 있는 것이 맞습니다.
@infikei 혹시, 해당 반례 코드 제 coding repo에 contributor로 등록하고, git repo에 올려도 되나요?
21771번 - 가희야 거기서 자는 거 아니야
헉... 생각도 못한 케이스네요. 앗....
어떻게 접근하신 건지는 코드 분석을 해 보겠습니다.
저 경우는 2 x 5짜리 가희가 4 x 5짜리 베개 위에서 자고 있는 것이 맞습니다.
@infikei 혹시, 해당 반례 코드 제 coding repo에 contributor로 등록하고, git repo에 올려도 되나요?
@chogahui05 네 해당 반례 코드 contributor로 등록하고 repo에 올려주셔도 괜찮습니다 :D
예전에 통과했던 코드(48202854)에서는 P가 처음으로 나오는 행을 탐지하고, 그 행에서 P가 처음으로 나오는 열을 탐지하고, 그 칸을 왼쪽 위로 해서 베개의 크기만큼 직사각형 모양으로 검사하는 방식으로 잘못 구현했었습니다.
이렇게 하면 원래 베개가 있는 첫번째 행을 모두 가희가 차지하고 있으면서(위에 누워있으면서) 베개가 방의 아래쪽에 딱 붙어있는 데이터가 입력으로 들어왔을 경우 잘못된 답을 출력하게 됩니다.
이번에 문제를 다시 풀다가 아무래도 예전의 방법이 너무 이상해서 자세히 살펴보다가 우연히 발견했네요..
뭔가 설명이 복잡한 것 같아서, 위 설명에 속하는 비슷한 데이터들도 댓글에 함께 추가했습니다. (이 데이터들 역시 48202854 코드에서 걸러내지 못하고 통과되었어요)
p.s. 출제자님께서 직접 답글 남겨주시다니 영광입니다.. 확인해주셔서 감사합니다 :)
+ 아, 그리고 문제를 여러번 읽다가 알게 되었는데, 본문에 베게 -> 베개 오타가 있는 부분이 총 6곳이 있네요.. 오타는 글을 새로 올리는 게 나을지 모르겠지만 까먹기 전에 일단 여기에 적어봅니다..!
코드를 분석해 보니, 아래 예제도 비슷한 원리이네요.
우상단 부분을 잘못 가정해서 생긴 문제로..
(아마 좌상, 우상, 좌하, 우하단에 대해서 찾고 그것을 기준으로 탐색하는 경우) 비슷한 원리로 저격이 가능하겠네요.
이거 제대로 추가하면 걸릴 사람들 생각보다 있겠네요.
pycharm에서 닉네임 검색으로 하려 했으나, 안 되어서 git desktop으로 하였습니다.
해당 커밋에 공동 author로 등록하였습니다. 코드 세세히 분석해 보니 데이터가 약했네요... ㅠㅠ
덕분에 깃도 공부 하고 갑니다.
댓글을 작성하려면 로그인해야 합니다.
infikei 3년 전 1
예전에 구현을 잘못 했는지 코드가 이상해서 오늘 다시 짜다가 반례를 발견한 것 같아요.
예전 코드는 0을 출력하고, 오늘 코드에서는 1을 출력하는데 두 코드 모두 통과되었습니다.
- 예전 코드 (제출번호 48202854) : https://www.acmicpc.net/source...
- 오늘 코드 (제출번호 65759743) : https://www.acmicpc.net/source...
아래 데이터가 문제의 조건에 어긋나지 않는다면 데이터 추가가 필요할 것 같습니다. (다 확인해보진 못했으나 비슷한 케이스들이 더 있는 것 같아요)
한번 확인해주시면 감사하겠습니다.
+ 문제를 계속 보다가 오타를 발견하게 되어 여기에 함께 추가합니다.
문제 설명에 베개와 베게가 혼용되어 적혀있습니다. 베게 -> 베개 총 6곳 오타 수정 부탁드립니다.