2041번: 숫자채우기
N×M 크기의 격자에 적절히 수를 채우려 한다. 단, 인접한 수들의 차이로 1부터 (2NM-N-M)까지의 수가 한 번씩 나오도록 채우려 한다. N=2, M=2인 경우를 예로 들면 다음과 같은 방법이 있다. 위와 같
www.acmicpc.net
요즘 여기저기서 많이 보이는 문제이다.
다이아문제인데, 애드혹과 구성적 태그가 달려있길래 나도 도전해 보았다.
처음으로 푼 다이아 문제인데, 혼자 풀어내서 정말 행복하다 ㅎㅎ!
문제를 이해하는 것은 어렵지 않다.
인접한 원소의 차이가 1부터 2NM-N-M까지 모두 나오는 행렬을 만들면 된다.
두 개의 풀이가 있다.
첫 번째 풀이는 나의 풀이고 두 번째 풀이는 동기 meque98의 풀이이다.
두 풀이 모두 4칸씩 볼 때, 차이 2개를 정해주면 나머지 2개의 차이를 그에 맞춰 지정해주면 된다는 아이디어를 사용하였다.
그림을 보면 무슨 말인지 이해하기 쉬울 것이다.
검은색 숫자가 행렬이다.
빨간색 숫자는 인접한 칸의 차이이다.
하늘색 형광펜은 차이를 4개로 묶은 것 중 하나이다.
풀이 1의 하늘색 부분을 보면 5+8=4+9이다.
풀이 2의 하늘색 부분을 보면 7+18=12+13이다.
어떻게 4개를 뽑던 위와 같은 규칙을 만족하게 행렬을 만들면 된다.
직접 몇 개를 찾다보니
위의 2개의 수를 정하면 아래 2개의 수를 딱 맞게 배치할 수 있다는 사실을 알아내었다.
티어에 비해 생각보다 답은 간단하다.
신기하고도 신기한 애드혹의 세계
조금 더 좋은 풀이나 증명(?)법이 있으신 분들은 댓글로 알려주세요!!!
'PS > 백준' 카테고리의 다른 글
| [백준] 24979 COW Operations (2) | 2022.08.31 |
|---|---|
| [백준] 8479 Godzilla (C++) (5) | 2022.04.05 |
| [백준] 2325 개코전쟁, 2307 도로검문 (C++) (4) | 2022.02.13 |
| [백준] 1671 상어의 저녁식사 (C++) (0) | 2022.02.12 |
| [백준] 1017 소수 쌍 (C++) (6) | 2022.02.10 |