어제 학원끝나고 slither.io라는 지렁이게임을했습니다. 생각보다 재밌더군요 ㅎ
게임에서는 한 지렁이의 머리와 다른 지렁이의 몸통이 부딪히면 머리가 부딪힌 지렁이가 죽습니다.
게임을 하다가 생각난 문제인데 잘 안풀려서 올립니다....
우선, nxn 모양 칸에 1x2 크기의 지렁이들을 겹치지 않게 배열합니다.
이때, 지렁이의 머리와 꼬리를 각각 칸 1개라고 생각하고, 머리와 머리가 부딪히지 않게(가로 또는 세로로 직접적으로 부딪혀야합니다) 배열하는 방법이 몇가지일까요...?(n은 짝수)
꼬리
머리 or (꼬리 머리) (머리 꼬리) 이렇게 만나야 부딪히는걸로 생각합니다
머리
꼬리
생각해본 방법은 여러가지인데
지렁이의 머리를 O, 꼬리를 X라 두고 n*n에 O들끼리 만나지 않게 배열하는 가짓수로 바꿔봤는데 좀처럼 답이 나오지않네요ㅠ
고수분들 도와주세요!
대충 이렇게요
+ 돌려서 같은 모양은 하나로 셉니다
댓글 8
댓글 작성하기
-
+ 복귀?
-
조오금 생각을 해보니까 저기서 O만 8개를 배열하는건 어떨까 싶습니다
그런데 O주변이 모두 O일 수는 없으니, 그런 경우를 빼는건 어떨까요
-
일단 1*2 도미노를 짝수*짝수 격자판에 놓는 경우의 수 (https://wikimedia.org/api/rest_v1/media/math/render/svg/1bc328b90d68fd765e2666ad0c62bb42b2e2bd10)
에서 머리가 맞닿는 경우의 수를 빼는 식으로 해보면 되지 않을까요?
영어를 할 줄 아신다면 이게 도움이 될듯 해요.
닫기
