요즘 재밌는 문제가 많이 생각나서 좋습니다
그럼 문제 나갑니다.
| R | R | R | D | D | D |
| R | U | U | G | D | L |
| U | D | D | L | L | L |
| D | L | D | U | L | L |
| R | R | R | D | U | U |
| U | U | L | R | L | U |
윗 표와 같이 36개의 버튼을 가진 어느 금고의 문이 있다. 이 금고는 다음과 같은 규칙으로 버튼을 눌러야 열린다고 한다.
1. 누른 버튼에 L이 적혀있다면 왼쪽, R이 적혀있다면 오른쪽, U가 적혀있다면 위쪽, D가 적혀있다면 아래쪽에 있는 버튼을 누른다. 몇 칸을 이동하는지는 자유다.
2. 같은 영어가 적힌 버튼은 위치가 다른 버튼이라도 연속해서 두 번 이상 누를 수 없다.
3. 시작하는 위치는 자유이나 모든 버튼을 한번씩만 누르고 최종적으로 G를 눌러야한다.
금고를 열 수 있겠는가?
ak2357님의 추가 문제: 금고를 여는 경우의 수는 모두 몇가지인가?(tip: ak2357님의 시작지점과는 다른 곳에서 시작해도 가능한 곳이 존재합니다. 되돌아 가는 것도 일단은 가능하단걸 잊지마세요!)
좋아요
0
글쎄요
0
어려워요
0
-
문제 오류인가요? 같은 알파벳을 2번 이상 누를 수 없다면 어차피 전체를 다 누를 수 없는데...
-
연속해서 누를 수 없다는 말일까요...?
좋아요0 -
답 : 가능하다
실례를 찾을 수 있습니다. 알파벳 위에 쓰인 숫자는 누르는 버튼의 순서를 뜻합니다.
이것은 n번째 버튼을 지날 때 무조건 눌러야 하는 (n-1)번째 버튼 또는 그 반대의 경우의 버튼들을 이어서 만든 루프입니다. 그리고 출발 지점은 항상 G옆의 D입니다. 끊이지 않고 한 버튼에서 다른 버튼으로 가기 위해서는 한 행 또는 열에 가로 이동(R,L) 또는 세로 이동 (U,D)의 개수의 차이가 2의 배수여야 합니다. 하지만 2번째 행과 4번째 열에서는 개수가 1차이 나므로 시작점은 항상 2번째 행 또는 4번째 열 위에 있습니다.
시작점으로 가능한 경우가 D밖에 없으므로 D는 항상 시작점이고 도착 마지막 버튼은 항상 4번째 열에 위치합니다.추가 문제: 모든 버튼을 누르고 G까지 가는 모든 경우의 수는? (단, 문제의 조건은 원래와 같다)
좋아요0 -
약간 오해의 소지가 있었네요, 같은 영어를 연속해서 누르는게 불가능하다는 의미입니다, ak님 경로의 가지수까지 구하셨다니 대단해요, 추가문제로써 달아두겠습니다
좋아요0
-
-
