유튜브에서 문제랑 해설 봤는데 재밌어서 한번 올려봄 ㅋㅋㅋ
해당 문제는 올해 국제 수학 올림피아드 5번 문제임.
빠른 파악을 위해 미사여구 최대한 빼고 요약했음.
문제 : 2024개의 행(가로줄), 2023개의 열(세로줄)로 이루어진 보드판에서 게임을 하려고 한다. 1행의 아무칸에서 시작해서 2024행의 아무칸에나 도달하면 되는 게임이다. 다만 시작행(1행)과 도착행(2024행)을 제외한 행에는 괴물이 1마리씩 숨어있고 괴물들은 서로 각자 다른 열에 있어서 총 2022개의 괴물이 숨어있다. 괴물을 만나면 이번 시도가 끝난 것으로 다시 1행에서 시작해야 한다. 당신은 인접한 상하좌우의 칸으로만 이동할 수 있으며 갔던 칸으로 돌아가도 됨. 괴물만 안 만나면 됨! 당신은 어떤 전략을 사용해서 많아야 n번의 시도만에 클리어할 수 있다면 이 n의 값은 무엇인가?
한번 풀어보지! 어려우면 밑에 힌트도 있음.
코딩하는 게이는 더 느꼈을텐데 뭔가 백준에 있는 문제랑 비슷하지?
힌트
1. 10000개의 행, 9999개의 열에서 9998개의 괴물이 있는 상황이여도 답은 같음.
2. 확실한 세이프존을 찾아내는 것. 이것이 핵심임.
3. 괴물 위치가 확정됐다면 그 행은 목숨을 잃지 않고 다음행으로 넘어갈 수 있겠지?
이런 문제 특) 정답은 작은 숫자임 ㄹㅇㅋㅋ
혹시 문제에서 괴물이 있는 칸인지 판별하는 방법이 따로 있었노? 아니면 괴물이 있는 칸에 가야지만 괴물이 있는지 판별이 가능함?
괴물과 직접 조우해서 목숨을 잃거나 남은 경우의 수에 따라 괴물일 수 밖에 없다고 추리하는 것 뿐임. 그래서 많으면 2트를 괴물 찾는데 써야해서 최대 3트에 깨는 전략이 최고 전략임
지가 이해가 안되서 그런데 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 위와 같은 경우에는 어떤 식으로 해결을 해야 하노?
1행 괴물이 끝에 있고 2행 괴물이 대각선에 있는 경우에 해당되는 건데 혹시 이해가 잘 안됐노
0 0 0 0 01 0 0 0 00 1 0 0 00 0 1 0 00 0 0 1 00 0 0 0 0인 상황에서 1트를 소비해서 1행의 괴물 위치를 찾았다고 하자. 그러면 대충 이런 상황이겠지?0 0 0 0 01 0 0 0 00 ? ? ? ?0 ? ? ? ?0 ? ? ? ?0 0 0 0 0왼쪽 끝에 있으므로 오른쪽 끝에서 2행으로 내려감그리고 왼쪽으로 가다보면 (H가 현재 위치)0 0 0 0 01 0 0 0 00 ? H 0 0이렇게 될 거임. H는 현재 위치이니 당연히 0이고 1일 수 있는 칸은 하나밖에 없지?목숨을 쓰지 않고 괴물의 위치를 알아냈음. 이러면 다시 오른쪽 끝으로 돌아가서 3행으로 내려가고이를 반복함. 또 목숨 안 쓰고 괴물 위치 알아냈고 다시 돌아가서
내려가고... 이게 계속 반복되겠지? 결국 2트만에 깸 (사실 처음부터 오른쪽 끝에서 찾았으면 1트만에 깰 수 있음) 즉, 양쪽 끝 중 하나에 1행의 괴물이 있으면 1~2트만에 클리어하고 중간에 있으면 최대 3트가 걸리므로 이 전략은 최대 3트가 필요한 전략임. 이것보다 최대 필요 트라이가 더 적은 트라이가 들어가는 전략은 없으므로 최대 3트가 필요한 이 전략이 답임
그러면 첫번째 괴물의 위치에 따라서 두번째 시도에서 시작 및 행동 방법이 달라지는게 맞노? 1) 첫번째 괴물의 위치가 가장자리가 아닐 경우 -> 아무 곳에서 시작하더라도 상관 X 2) 첫번째 괴물의 위치가 가장자리인 경우 -> 가장 먼 곳에서 괴물의 위치를 유추한다 이런 식으로
ㅔㅔ 근데 행동 방법은 달라져도 되고 같아도 됨. 행동 목적은 똑같으니까 결국 괴물의 위치 하나가 확정되면 그 아래로 안전 구역임이 확정되며 확정 클리어 루트가 생기게 됨 즉, 기본적으로 1행의 괴물 위치 확정 → 1행의 괴물 아래로 가는 방법 탐색이 기본 행동 원리임 1행 괴물 아래로 가려면 결국 2행의 괴물이 대각선 아래에 있느냐가 중요하겠지? 1행 괴물이 가장자리가 아니면 그 아래로 가는 방법이 2가지이므로 2행 괴물이 대각선 중 하나에 있어도 2트에 그걸 발견하고 3트에 무조건 깨게 됨 다만 가장자리에 있을 때 대각선으로 2행 괴물이 있으면 아예 루트가 사라지므로 주의해야 함. 따라서 대각선으로 있지 않은 괴물을 한 번이라도 찾으면 바로 클리어 루트를 찾게 됨. 이때 반대편에서 시작하는 이유는 대각선
에 있는 괴물은 추리를 통해 확정시킬 수 있음. 대각선에 없으면 그냥 그 트라이를 소모해서 확정 루트를 알아내게 됨. 모두 대각선으로 있으면 2트에 깨게 되고 하나라도 대각선에 없으면 2트 째에 목숨 써서 확정 루트 알아내고 3트에 깨게 됨 결과적으로 1행 괴물을 찾고 그 대가선 아래에 다음 괴물이 있느냐를 찾아내는 것이 핵심이기 때문에 괴물1이 가장자리가 아닐 때 아무 곳에서 시작해도 되고 아니면 가장자리일 때랑 알고리즘 동일하게 가장 먼 곳에서 시작해도 되고 아니면 가장 빠르게 수행하게 1행 괴물의 대각선 위에서 시작해도 됨