수학동아 - 폴리매스

함께 풀고 싶은 문제

창의력을 기를 수 있는 수학 문제 또는 퍼즐을 내는 곳입니다.

[창의 퍼즐] 나이트가 도착할 수 있는 칸의 개수는?

Nicholas 2018.03.18 21:02 조회 1128

문제 푼 사람 0명

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

책에서 본 문제인데 이런 문제입니다.

Q . 크기가 무한대인 체스판의 검은색 원점에 나이트가 있다. 나이트가 n번 움직였을때 도착할 수 있는 칸의 개수를 구하여라.

제가 규칙을 찾아서 식을 세우긴 했는데 맞는지 모르겠어서요.... 코딩을 통해서 n이 1,2,3,4,5,6,7,8,9.......일때 칸의 개수가 각각 몇인지 알 수 있는 방법 아시는 분 계시면 어떻게 프로그래밍 해야하는지 알려주시면 감사하겠습니다. 엄밀하게 증명된 답과 그 과정도 환영합니다!

이전글 완전제곱수가 되는 모든 k값

다음글 무한 호텔방 문제의 한단계 더

이 문제 어떠셨나요?

글쎄요

어려워요

문제 찜하기 목록보기

댓글 작성하기

여백 패르마 Lv.5 2018.03.19 04:23

다시 돌아오는 것도 가능한가요? 즉, 그 경우도 포함인가요??

댓글 작성하기 좋아요0 댓글수1
- Nicholas Lv.1 2018.03.19 16:15
  
  네. 그 경우도 포함입니다.
  
  좋아요0
수달 Lv.1 2018.03.23 08:49

나이트가 말모양으로 장기의 말과 가는 칸 수가 같죠?

댓글 작성하기 좋아요0 댓글수1
- 수달 Lv.1 2018.03.23 08:49
  
  체스를 안 둬 봐서....
  
  좋아요0
베네딕트0724 Lv.6 2018.03.25 09:08

프로그래밍 해보긴 했는데 4개 이상은 컴퓨터 성능이 매우 뛰어나지 않은 이상 도저히 안 됩니다. 아직 약간의 오류가 있어서 수정한 뒤에 알려드리겠습니다.

댓글 작성하기 좋아요0 댓글수0
베네딕트0724 Lv.6 2018.03.25 22:29

#include <stdio.h>

int count=0, x=0, y=0;
int a[10000]={0,};
int b[10000]={0,};
int c, d;
int move(int i){
int j, t;
if(i>0){
  c=x, d=y; x+=2, y++; move(i-1);
  c=x, d=y; x+=2, y--; move(i-1);
  c=x, d=y; x-=2, y++; move(i-1);
  c=x, d=y; x-=2, y--; move(i-1);
  c=x, d=y; x++,y+=2;move(i-1);
  c=x, d=y; x++, y-=2; move(i-1);
  c=x, d=y; x--, y+=2; move(i-1);
  c=x, d=y; x--, y-=2; move(i-1);
  return count;
}
if(i<=0){
  t=1;
  for(j=0;j<=count;j++){
   if((a[j]==x)&&(b[j]==y)){
    t=0; break;
   }
   break;
  }
  if(t){
   a[count]=x; b[count]=y;
   count++;
   x=c, y=d;
  }
}
}
void main(){
int n;
for(n=1;n<=3;n++)
  printf("n=%d : %d\n", n, move(n));
}

오류가 완벽하게 수정되지는 않았습니다. n=2일 때 65라고 결과가 나오니까요.........

댓글 작성하기 좋아요0 댓글수0
베네딕트0724 Lv.6 2018.03.26 02:12

A PHP Error was encountered

Severity: Warning

Message: mkdir(): Permission denied

Filename: libraries/Common.php

Line Number: 202

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 202
Function: mkdir

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: file_put_contents(/DATA/upload/polymath/latex/02f515f9126a996870ad6e79ec1acb46.gif): Failed to open stream: No such file or directory

Filename: libraries/Common.php

Line Number: 213

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 213
Function: file_put_contents

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

오류 수정했습니다. 정답이 맞는지는 모르겠습니다.

#include <stdio.h>
int count=0, x=0, y=0;
int a[10000]={0,} , b[10000]={0,};
int c, d;
int move(int i){
int j, t;
if(i>0){
  c=x, d=y; x+=2, y++; move(i-1);
  c=x, d=y; x+=2, y--; move(i-1);
  c=x, d=y; x-=2, y++; move(i-1);
  c=x, d=y; x-=2, y--; move(i-1);
  c=x, d=y; x++,y+=2;move(i-1);
  c=x, d=y; x++, y-=2; move(i-1);
  c=x, d=y; x--, y+=2; move(i-1);
  c=x, d=y; x--, y-=2; move(i-1);
  return count;
}
if(i<=0){
  t=1;
  for(j=0;j<count;j++){
   if((a[j]==x)&&(b[j]==y)){
    t=0; x=c; y=d; break;
   }
  }
  if(t){
   a[count]=x; b[count]=y;
   count++;
   x=c, y=d;
  }
}
}
void main(){
int n;
for(n=1;n<=10;n++){
  count=0;
  for(x=0; x<=10000; x++){
   a[x]=0, b[x]=0;
  }
  x=0; y=0;
  printf("n=%d : %d\n", n, move(n));
}
}

n=1일 때 : 8

n=2일 때 : 32

n=3일 때 : 68

출력 결과

이 이상은 구하는데 너무 오래 걸려요......... 재귀함수를 이용했는데 n에 따라 함수의 실행 횟수가 $8^{n}$ 이나 되서..... 좀 빨리 실행할 수 있는 건 모르겠고, 이 코드에 대해 설명드릴게요

메인 함수에서, x의 좌표값과 y의 좌표값을 0으로 설정하고 move함수를 실행시킵니다. move함수에서는, 나이트가 이동할 수 있는 8가지 이동을 하나하나 실행하면서, n의 횟수, 즉 이동 횟수를 1씩 줄입니다. n이 0이 되면, 배열 a에 저장된 x좌표, b에 저장된 y좌표에 동시에 공통되는 것이 있는지 확인합니다. 있으면, count를 증가시키지 않고, 없으면, 배열에 저장시킨 후 count++를 합니다. 재귀호출된 함수가 8가지 이동을 모두 해보고, count를 반환하는데, 재귀호출된 함수에서는 반환값이 중요한 게 아니라, a배열과 b배열의 저장한 값, 그리고 count의 증가가 중요한 겁니다. 그리고 move함수가 모두 끝나고 나면, count를 반환합니다. 그래서 printf("n=%d : %d\n", n, move(n));이 구절에서 저런 형식으로 출력이 됩니다. count가 외부변수이기 때문에 굳이 반환할 필요는 없습니다.

중요한 점 : a배열, b배열, count, x,y, c, d는 모두 외부변수여야 합니다.내부변수인 경우에는 move함수를 호출할 떄마다 변수들이 초기화됩니다.

댓글 작성하기 좋아요0 댓글수0
muse Lv.6 2018.04.04 03:41

/// copyright by muse.

#include <bits/stdc++.h>

int n; /// 움직이는 횟수.

bool board[102][102]; /// 체스판. (50, 50)이 원점이라고 가정합니다.
bool DP[52][102][102]; /// 한 번 계산한 위치는 다시 계산하지 않게 처리합니다. 즉 한 번 계산한 위치에 표시를 해 놓습니다.

int xx[]={-2, -1, 1, 2, 2, 1, -1, -2}, yy[]={1, 2, 2, 1, -1, -2, -2, -1};
/// 나이트가 움직일 수 있는 칸 수를 설정해 놓은 배열입니다.

int ans; /// 답을 저장할 변수입니다.

void move(int i, int x, int y){ /// i는 지금까지 움직인 횟수, x, y는 위치.
if(i==n){ /// n회 움직였을 때(즉 다 움직였을 때)
board[x][y] = true; /// 체스판에 체크를 해 놓습니다.
return; /// 함수를 종료합니다.
}
if(DP[i][x][y]) return; /// 이미 방문한 위치이면 함수를 종료합니다.
DP[i][x][y] = true; /// 방문한 위치에 체크합니다.
for(int a=0; a<8; a++){ /// 방문할 수 있는 모든 위치를
move(i+1, x+xx[a], y+yy[a]); /// 방문합니다.
}
return; /// 모든 작업이 끝났으므로 프로그램을 종료합니다.
}

int main(){
scanf("%d", &n); /// 움직일 횟수를 입력받습니다.
move(0, 50, 50); /// 함수를 호출합니다.
for(int i=1; i<=100; i++){
for(int j=1; j<=100; j++){ /// 모든 칸을 방문하며
ans += board[i][j]; /// 방문할 수 있는지를 체크합니다.
}
}
printf("%d", ans); /// 결과를 출력합니다.
}

저는 수학장 님과는 다른 결과가 나오네요.

1: 8

2: 33

3: 76

4: 129

5: 196

6: 277

7: 372

8: 481

9: 604

10: 741

.....

24(구할 수 있는 최대): 4129.

그 이상은 답이 이상하게 나오거나 에러가 나옵니다.

댓글 작성하기 좋아요0 댓글수0
Koo Lv.1 2018.04.14 18:55

정확히 n번 움직이는건가요 아니면 n번까지 움직일 수 있는 건가요?

댓글 작성하기 좋아요0 댓글수0

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property Article_model::$best_cnt is deprecated

Filename: ver3/Article_model.php

Line Number: 18

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/models/ver3/Article_model.php
Line: 18
Function: _error_handler

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 322
Function: model

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 392
Function: getFloatingMyInfo

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property Article_model::$popular_cnt is deprecated

Filename: ver3/Article_model.php

Line Number: 19

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/models/ver3/Article_model.php
Line: 19
Function: _error_handler

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 322
Function: model

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 392
Function: getFloatingMyInfo

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property Contents::$article_model is deprecated

Filename: core/Loader.php

Line Number: 353

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 322
Function: model

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 392
Function: getFloatingMyInfo

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property CI_Loader::$article_model is deprecated

Filename: core/Loader.php

Line Number: 925

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 434
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

수학동아 - 폴리매스

본문바로가기

닫기

지금 바로
로그인해보세요

로그인 하기

로그인 하면 내가 찜한 문제와 수행 평가를 한곳에서 볼 수 있어요!