본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[폴리매스 문제] 게으른 팩맨 게임
수학동아 2019.10.03

 

*이번 달은 신희성 교수님의 조언을 받아 김홍녕 학생(서울과학고등학교 3학년)이 친구들에게 소개하고 싶은 문제를 출제합니다.smiley

 

 

좌표평면의 제 1사분면 위에 점 n개가 무작위로 놓여있다. 점을 좋아하는 팩맨은 x, y 좌표축에 평행한 방향으로만 전진할 수 있다. 예를 들어 n이 1, 2일 때 각각 2, 3번 전진하면 점을 모두 먹을 수 있다.  

 

 

 

 

문제

 

점들의 배치에 관계없이 팩맨은 k번 전진해서 모든 점을 먹을 수 있다. 팩맨이 원점 위에 있을 때 k의 최솟값은 무엇일까?

 

 

-끝-

 

 

  •  
    시그마 Lv.4 2019.10.04
    확인요청중

    뭔가 k = n + 1같은 느낌이 드는걸요?

    그런데 모든 점이 x = 0이면 1번밖에 필요하지 않기 때문에 더 생각해 볼 필요는 있을 것 같습니다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      cube120 Lv.4 2019.10.04

      점이 1사분면에 있으니까 x=0인 경우는 고려하지 않아도 될 것 같네요.

      그리고 '배치에 상관없이'라는 말이 있으므로 최악의 상황만 고려해도 충분합니다.

      좋아요0
    •  
      시그마 Lv.4 2019.10.05

      행복한 착각이네용

      좋아요0
  •  
    똘이 Lv.2 2019.10.05

    k의 최솟값은 숫자로 구할 수 있는건가요? 문자는 안되나요??

    댓글 작성하기 좋아요0 댓글수1
    •  
      디듀우 Lv.6 2019.10.05

      n에 대한 식이 아닐까요

      좋아요0
  •  
    무한대의끝을본남자 Lv.6 2019.10.05

    A*알고리즘 써도 되지않나요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    구머 Lv.3 2019.10.05

    일단 상한을 n+sqrt(n)정도로 좁히긴 했는데 더 가능할진 모르겠네요

    댓글 작성하기 좋아요0 댓글수1
    •  
      리프 Lv.6 2019.10.07

      혹시 가능하다면 풀이도 올려주실 수 있나요?

      좋아요0
  •  
    아몬드 먹는 몰랑✅ Lv.8 2019.10.05

    제 생각에는 일단 점을 지나려면 그점과 x좌표값이나 y좌표값이 같아야 되자냐요. 최악의 상황을 고려했을때(모든 점들의 x좌표값과 y좌표값이 다를때) x좌표를 처음에 맞춘다고 하면 한 번을 움직이고 그다음 첫번째 점을 지나면서 두번째 점과 y좌표를 맞추고 이 과정을 반복하면 시그마님의 말처럼 n+1번이면 될 것 같네요

    댓글 작성하기 좋아요1 댓글수1
    •  
      시그마 Lv.4 2019.10.05

      시각화하면 달팽이 모양이 되지요 (^오^)

       

      좋아요0
  •  
    손성민 Lv.4 2019.10.05

    이거 꽤 재미있기도하고 어렵기도해요.

    댓글 작성하기 좋아요0 댓글수0
  •  
    리프 Lv.6 2019.10.05

    n=3일 때 점의 위치가 (1,3), (2,1), (3,2)이면 5번 필요하지 않나요?

    이렇게 되면 k=n+1이나 구머님이 말씀하신 n+sqrt(n) 값이 잘못 된 것 같은데요

    댓글 작성하기 좋아요0 댓글수5
    •  
      시그마 Lv.4 2019.10.05

      4번입니다.

      좋아요0
    •  
      시그마 Lv.4 2019.10.05

      짠!!

      좋아요0
    •  
      리프 Lv.6 2019.10.05

      ㅇㅎ 4번이면 되네요

      그런데 k=n+1은 확실히 아닙니다. (반례는 밑에 구머님 댓글 참고)

      좋아요0
    •  
      cube120 Lv.4 2019.10.06

      잉? 제가 착각하는건진 모르겠는데

      n=3일때 k=5 아닌가요?

      좋아요0
    •  

      cube120님의 경우에서는 5개가 필요한 것이 맞습니다.

      그러면 n=3일때 k=5이겠네요

      좋아요0
  •  
    구머 Lv.3 2019.10.05

    답을 n+1로 추정하는 분들이 좀 계신것 같은데 (1,1) (4,2) (2,4) (5,5)로 하면 n=4일때의 반례가 됩니다

    댓글 작성하기 좋아요0 댓글수0
  •  
    ………………………… Lv.10 2019.10.05 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    ………………………… Lv.10 2019.10.05 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수3
    •  
      김우현 기자 Lv.4 2019.10.06

      2n-1이 최솟값임을 증명할 수 있나요~??surprise

      좋아요0
    •  
      ………………………… Lv.10 2019.10.06 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      B.C.I.수학장 Lv.5 2019.10.06

      2n-1이 최솟값이라면, n=1일 때 1번 안에 점으로 이동할 수 있다는 뜻이 됩니다. 점의 위치를 (1,1)이라고 합시다. x축의 방향으로 1만큼, y축의 방향으로 다시 1만큼. 총 2번 움직여야 하므로 모순입니다.

      좋아요0
  •  
    권동주 Lv.1 2019.10.06

    [n/3] + n+1이 아닐까요,

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

      이동하는 횟수는 정수인데 2가 오면 분수가 되잖아요.

      좋아요0
    •  
      디듀우 Lv.6 2019.10.08

      그래서 가우스 기호 씌우신 것 아닐까요?

      좋아요0
  •  
    21세기오일러 Lv.10 2019.10.06

    n+\left [ ^{\sqrt{n}}\right ]+1이면 되지 않을까요?

    (대괄호는 가우스함수입니다.)

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

      n=1에서 3이 되어버리는데요

      좋아요0
    •  
      21세기오일러 Lv.10 2019.10.06

      최대가요.

      좋아요0
    •  
      cube120 Lv.4 2019.10.06

      음... 혹시 \mathrm{sup}\left \{ k \right \}=n+\left \lfloor \sqrt n \right \rfloor+1 인 이유가 있을까요?

       

      좋아요0
    •  

      1에선 2하면 충분한데요

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2019.10.06

      휠릭스님, n이 1일 때 k의 값이 3이 나온다고 틀린 건 아니라고 생각합니다. 휠릭스님 말씀대로 n이 1일 때는 2번으로 충분한데, 3번으로는 당연히 가능하지 않겠습니까? 이 문제는 좀 애매한 것 같네요. 만약 문제가 모든 n에 대해서 성립하도록 하는 것으로 해석될 수도 있고, 어떤 n에 대해서도 k번 움직였을 때 모든 점을 이동할 수 있게 k를 구하는 문제로도 해석될 수가 있습니다. 만약 전자라면 n이 1일 때 k의 값이 2여야만 하겠지만, 후자일 때는 n이 1일 때 k의 값이 2 이상이기만 해도 충분하다고 생각합니다.

       

       전 문제의 의도가 후자인 것 같습니다. 따라서, 어떤 n에 대하여 k-1번 안에 불가능한 경우를 찾고, 모든 n에 대하여 k번 안에 항상 가능하다는 것을 증명하는 것으로 충분합니다

      좋아요0
  •  

    하지만 k의 값이 최소가 되게 해야 합니다.

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

    제가 정리를 한번 해 보니

    n 1 2 3 4
    k 2 3 5 6

    이 됩니다. (n이 4보다 크면 k는 2씩커짐)

    범위를 나눌 수 있다면 좋을 것 같은데

    댓글 작성하기 좋아요0 댓글수1
    •  
      B.C.I.수학장 Lv.5 2019.10.06

      n이 4면 6번 안에 충분하지 않나요? 혹시 반례가 있을까요?

      좋아요0
  •  
    B.C.I.수학장 Lv.5 2019.10.06

    추측입니다만 \left [ \frac{4}{3}n \right]+1 일 것 같습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    B.C.I.수학장 Lv.5 2019.10.06

    상한이 \left [ \frac{4}{3}n \right ]+1이라는 것을 증명할 수 있습니다. 일단, 가장 바깥쪽, 즉 가장 오른쪽, 위쪽, 아래쪽, 왼쪽의 점을 잇는 가장 작은 직사각형을 그립시다. 그 안쪽에 다른 모든 점들이 있습니다. 이 점들의 가장 바깥쪽의 점을 잇는 직사각형을 그리는 시행을 가장 안쪽에 점이 0~2개 남을 때까지 반복합니다.

     

    두 개 이상의 점이 동일한 x혹은 y값을 가지지 않는다고 합시다.(두 개 이상의 점이 동일한 x값 혹은 y값을 가지면 더 많은 이동이 필요한 점들이 존재) 각 직사각형에는 2개에서 4개까지의 점이 있을 수 있다.

     

    i) 직사각형에 2개의 점이 놓여 있다.

     직사각형의 반대쪽 꼭짓점에 두 점이 놓여 있습니다.

     

    ii) 직사각형에 3개의 점이 놓여 있다.

     직사각형의 한 꼭짓점에 점이 놓여 있고 이 점과 만나지 않는 두 변에 점이 하나씩 놓여 있습니다.

     

    iii) 직사각형에 4개의 점이 놓여 있다.

     직사각형의 모든 변에 점이 놓여 있습니다.

     

    i의 점으로 가장 먼저 이동하고, ii, iii의 경우는 그 후 안쪽부터 바깥쪽으로 나오면서 점들을 먹습니다.

    첫 번째 이동 후, i의 점들은 2개당 2번의 이동, ii의 점들은 3개당 최대 4번의 이동, iii의 점들은 4개당 4번의 이동이 필요합니다.

    직사각형에 속하지 않은 점들은 i의 점들을 모두 먹고 먹으면 1개당 1번의 이동으로 먹을 수 있습니다.

     

    따라서 모든 점들이 ii인 상황일 때 한 점당 이동을 최대로 하며, 한 점당 최대 4/3번 이동합니다.

     

    최대로 이동하면

    점이 3m개일 때 4m+1

    3m+1개일 때 4m+2

    3m+2개일 때 4m+3

    이것은 \left [ \frac{4}{3}n \right ]+1과 같습니다.

     

    따라서 이 값이 상한이 됩니다.

     

     

    글로만으로는 무슨 말인지 모르겠으니 대댓글에 사진 첨부하겠습니다!

    댓글 작성하기 좋아요0 댓글수3
    •  
      B.C.I.수학장 Lv.5 2019.10.06

      좋아요0
    •  
      Simon Lv.2 2019.10.07

      이게 최적임을 보이는 걸 노력해야되겠군요

      좋아요0
    •  
      리프 Lv.6 2019.10.07

      구머님께서 상한을 n+sqrt(n)까지 줄였다고 하시는데 (k=3일 때 5인 경우가 있으므로 아마도 +1을 해야 할 것 같네요) 만약 구머님의 풀이가 맞다면 [4n/3]+1보다 작은 상한이 존재하기 때문에 상한을 더 줄일 수 있을 것 같네요

      좋아요0
  •  
    수학잘하고싶다 Lv.1 2019.10.07
    확인요청중

    /resources/comment/2019/10/349db40add4b01c2e7926361cfb226e5.jpg

    K=n+1 인것같습니다. 혹시 잘못된게 있으면 알려주세요

    댓글 작성하기 좋아요0 댓글수1
  •  
    구머 Lv.3 2019.10.07

    이런..제가 사기를 쳤군요 상한을 n+2[sqrt(n)]으로 줄였습니다. 이 값또한 1에서 2정도의 오차가 있을 수 있어요.

     

    일단 여러분도 직접 상한을 구해보면서 느끼셨을텐데, 팩맨을 오직 n번(혹은 처음꺼 포함해서 n+1번)안에 하려고 하다보면 팩맨이 어떤 점을 지난 후에 1번의 방향전환만으로는 다른 점을 못먹는 경우가 결국 존재하게 됩니다. 여기서 제가 생각한 아이디어는, "이 낭비되는 방향전환을 최소화하면 되겠다!"였고, 여기서 계단형으로 지그재그해서 팩맨를 이동시키면 그 경로 동안에는 낭비가 일어나지 않음을 관찰했습니다. 따라서 최대한 길이가 긴 계단을 탄다는 단순한 생각으로 접근을 하였고, 마침 폴리매스-(대한수학회9)번 문제에서 "n개의 점에는 적어도 [sqrt(n)]+1의 길이를 갖는 계단이 존재한다"라는 명제를 제가 증명해놨더군요. 따라서 한번에 계단을 최대한 타고, 남은 점들 중 가장 긴 계단으로 넘어가는 과정을 반복하면, n+2sqrtn이라는 결과를 얻게 됩니다.

    (조만간 그림설명 첨부 예정)

     

    또한 이 계단과 계단 사이를 지날때 가끔 낭비가 일어나지 않는 경우가 존재하는데, 아직 이에 대한 규칙은 잘 모르겠습니다..

    댓글 작성하기 좋아요0 댓글수0
  •  
    해결
    Fermat314 Lv.2 2019.10.08

    k=n+2(n이 3이상), n+1(n이 2이하)

    인 것 같습니다.

    증명은 사진으로 첨부합니다.(글씨가 좀 흐리네요...)

    4번의 예시에서 연두색 선은 7개, 주황색 선은 3개, 빨간색 선은 15개입니다.

     

    1번에서 직사각형을 선택하는 경우에 i), ii), iii) 외에도 세 점 이상이 직사각형의 꼭짓점에 위치하거나, 두 점이 꼭짓점에 위치하고 한 점이 변 위에 있는 등의 경우도 있을 수 있습니다. 또, 4번에서도 선을 그을 때 두 개 이상의 점을 지나는 예외적인 경우도 가능합니다. 그러나 이런 경우는 선을 긋는 횟수를 줄여주거나 다른 경우로 대체 가능하므로 이러한 경우가 논리 전개에 영향을 주는 것 같지는 않아 보입니다.

    마지막 빨간색 선 단계에서도 B에 속해있는 점이나 i)의 직사각형 위의 점의 순서에 상관없이 더 안쪽에 있는 점을 먼저 이으면 됩니다. 사진에서는 가장 안쪽의 B를 이은 선을 가장 안쪽의 i) 직사각형 변까지 뻗는다고 했는데, 경우에 따라 i)가 먼저일 수도 있고 그 다음 안쪽의 B가 먼저일 수도 있습니다. 4번 예시에서 빨간색 선은 i), B, B, i), i), B의 순서로 연결됩니다. 마지막 단계에서 점을 잇는 논리의 핵심은 항상 안쪽에서 바깥쪽으로 선을 뻗어나가는 방식으로 B, i)에 관계없이 점을 잇는것이 가능하다는 점입니다.

    엄밀한 증명은 생략할 테니, 부족하다고 느껴진다면 나머지 증명도 채워 주시면 감사하겠습니다.

     

     

    제가 한 증명이 맞는다면 이제 k=n+1을 만족하지 않는 경우가 항상 존재함을 증명하는 일이 남겠네요.

    댓글 작성하기 좋아요0 댓글수10
    •  
      Fermat314 Lv.2 2019.10.08

      지금 보니 제가 쓴 i), ii), iii)의 경우가 수학장님이 앞서 쓴 댓글에 이미 있군요. i로 표현한 것까지 같은 게 신기하네요 ㅋㅋ

      좋아요0
    •  
      Fermat314 Lv.2 2019.10.08

      k=n+1을 만족하지 않는 경우가 항상 존재함도 쉽게 증명 가능한 것 같습니다. 가장 바깥쪽의 직사각형이 iii)이면서 내부에 점이 존재하는 경우(따라서 n은 3 이상입니다.)를 보면, 일단 맨 처음에 1턴을 소모합니다. 그리고 가장 바깥쪽의 두 점을 더 이상의 턴 소모 없이 연속으로 이으려면 그 두 점보다 바깥쪽인 x축이나 y축에서 출발해서 두 점을 이어야 하는데, 이은 후에 내부에 있는 점으로 옮길 때 반드시 한 턴 이상이 필요하므로 총 두 턴 이상이 소모되어 n이 3이상일 때 k=n+1을 만족하지 않는 경우가 반드시 생깁니다.

      좋아요0
    •  
      구머 Lv.3 2019.10.08

      와 이게 되네요 개인적으로 ii)를 없애는 부분이 결정적이었던것 같습니다.

      좋아요0
    •  
      수돌이 Lv.2 2019.10.08

      (1,1), (2,2), (3,3)경우는 가장 바깥쪽의 직사각형이 iii)이면서 내부에 점이 존재하지만 4번만에 지날 수 있지 않나요?

      좋아요0
    •  
      Fermat314 Lv.2 2019.10.08

      그러네요.. n=3일 때 모든 점이 A나 B에 속해서 이런 예외가 생긴 것 같습니다. n=4일 때부터는 A와 B에 속한 점이 둘 다 있도록 항상 만들 수 있으니 k=n+1을 만족하지 않는 경우가 존재한다는 증명은 n이 4 이상일 때부터 성립한다고 수정해야겠네요.

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2019.10.09

      ㅋㅋㅋ 아이디어가 같다니 신기하네요. 점 잇는 방법 너무 잘 만드신 것 같아요!!

      좋아요0
    •  
      수돌이 Lv.2 2019.10.09

      n=5일 때도

      (1,1), (4,2), (3,3), (2,4), (5,5)이면 iii)의 A와 B에 속한점이 둘 다 있는데 이 경우도 n+1번에 지날 수 있어요! ㅠㅠ

      좋아요0
    •  
      Fermat314 Lv.2 2019.10.09

      수돌이 님이 말씀하신 대로 제가 위에서 한 'n이 3 이상일 때, k=n+1을 만족하지 않는 경우가 반드시 존재한다' 증명이 부실한 점이 있어서 다시 엄밀하게 하겠습니다.

       

      아래 사진은 n=3, n=4, n=5, n=6일 때 k=n+1을 만족하지 않는 경우입니다.

      귀류법으로 증명해보겠습니다.

      우선 아래 사진처럼 n=3일 때와 n=4일 때는 k가 각각 5, 6임이 자명합니다.

      n에 대하여 가장 바깥쪽 점이 A를 만족할 때, 즉 (1,1)과 (n,n)에 점이 있을 때를 가정합시다. k=n+1을 만족하기 위해서는 제일 먼저 가장 바깥쪽 점을 지나야 합니다. 그렇지 않으면 안쪽 점을 지난 후 바깥쪽 점 중 하나를 지날 때, 가장 바깥쪽보다 밖으로 나오게 되어 반대편 바깥 점을 지나는 것이 불가능합니다.

      가장 바깥쪽 점을 지난 후에는, 연속해서 반대편 점을 이을 경우 안쪽으로 가는 것이 불가능해지므로 안쪽 점의 모든 점을 이은 후 반대편 점을 마지막으로 잇는 경우밖에 없습니다. 즉, (1,1)을 제일 먼저 이은 후, 안쪽의 모든 점을 잇고, 마지막으로 (n,n)을 이어야 합니다((n,n)을 먼저 이으면 다음에 이을 점이 없습니다.). 

      그런데 n=5에서처럼 가장 바깥쪽 두 점을 제외한 안쪽 점들이 n=3과 같은 모양으로 배열된 경우, n=3일 때 k=5이므로 한 번에 안쪽 점들을 연결하는 것이 불가능합니다. (1,1)을 지나면서 시작해야 하므로 이는 n=3에서 x축 또는 y축에서 출발하는 경우와 같아지기 때문에, 시작 위치에 따른 예외형도 발생하지 않습니다.

      따라서 (1,1)과 (n,n)이 배열되어 있고, 안쪽 점들이 k=n+1을 만족하지 않는 n-2개의 점들의 배열로 이루어진 경우 n+1회 안에 모든 점을 통과하는 것은 불가능합니다. n=6일 때는 내부에 n=4의 배열이, n=7일 때는 내부에 n=5의 배열이 되는 식으로 가는 거죠.

      좋아요0
    •  
      수돌이 Lv.2 2019.10.09

      안녕하세요. '게으른 팩맨' 문제의 출제자 서울과학고등학교 3학년 김홍녕입니다.

      우선 축하드립니다! 맞는 풀이입니다. (제 풀이와 똑같아요!!)

       

      이 문제의 원형은 2019년 국제정보올림피아드의 문제입니다. 열 개의 그림 각각에서 k=n+3만에 모든 점을 지나는 경로를 그렸을 때 100점 만점을 받을 수 있었고, 시험장에서 아무도 만점을 받지 못하였습니다.

      문제를 보고 모든 경우에서 n+3이 최소일까? 라는 궁금증이 들었고, 임의의 점의 배치에 대해 최솟값을 구해보기로 했습니다. n이 3 이상일 때 n+3번만에 모든 점을 지날 수 있다는 사실을 증명했지만, 아직 n+2에 대한 반례가 나오지 않아 최솟값이 n+2와 n+3중 어떤 것인지 불투명한 상황이었습니다. 그 때 있었던 수학동아 인터뷰(멘토링?)에서 기자님에게 이 팩맨 문제를 전해드렸습니다.

      폴리매스 친구들과 함께 의견을 나누며 문제를 해결하고 싶었지만, 이 문제가 폴리매스에 올라오기 직전에 아쉽게도 우연히 풀어버리게 되었습니다. 제가 해결할 때까지는 2~3주나 걸렸기 때문에 상당히 오래 걸릴 것이라고 생각했습니다.

      그런데 5일 만에 해결될 줄은 상상도 못했습니다. 최대 크기 사각형을 잡는 수학장 님의 아이디어로 첫 단추가 순조롭게 꿰어졌으나, 그 이후가 까다로워서 적어도 n+3은 거치고 갈 줄 알았는데... 정말 대단하십니다!!ㅠㅠ 

      음 막 대학생이시고 그러셔서 제가 Fermat314님을 칭찬할 입장이 아닐 수도 있겠네요....ㄷㄷㄷ

      혹시 실례가 되지 않는다면 나이를 여쭤봐도 될까요?

      그리고 기자님께 연락드려서 최대한 빨리 해결 딱지를 붙여달라고 하겠습니다. 이 좋은 문제를 많은 사람들과 공유할 수 있어서 영광입니다!

      좋아요0
    •  
      Fermat314 Lv.2 2019.10.09

      아 수돌이님이 출제자셨군요 ㅋㅋ

      저는 현재 일반고에 재학중인 수능 36일 남은 고3입니다 ㅠㅠ 수돌이님이랑 동갑이죠.

       

      이 문제를 그저께 밤에 처음 보고 k=n+3까지는 생각했는데, k=n+2로 줄이는 게 어려워서 학교에서 고민하다가 우연찮게도 하루만에 풀렸네요. 저도 이렇게 빨리 푼 게 처음이라서 되게 신기하고 운이 좋았던 것 같아요 ㅋㅋㅋ

      좋아요0
  •  
    RedHood Lv.2 2019.10.09

    .....

    댓글 작성하기 좋아요0 댓글수0
  •  
    code Lv.4 2019.10.11
    확인요청중

    이미 해결되었지만... 제 추론이 답과 일치하여 이 풀이도 가능한지 궁금하여 작성해봅니다.

    처음에 어느 점에 도달할때, 팩맨의 방향은 2가지중하나입니다.

    그점이 (양, 양)의 위치를 가지고 각각에 따라 양이면 양방향 쪽으로만 점먹기가 마무리 되기때문에 x로하나 y로 하나해서 둘입니다.

     2개의 점이 남은 경우를 생각하겠습니다.

    만약에 마지막에 먹은 점이 그 두 점의 x 그리고 y좌표사이에 존재한다면,(다른경우가 있을 수도 있다)

    나아가던 방향을 이용해 하나를 소모해서 남은 한개와 2개를 소모해서 마지막점을 먹을 수 있습니다.

    .

       .(마지막으로 먹은 점)

                    .   ------(남은 2개의 점이 이루는 오름이나 내림의 경우 연결방향으로 들어갈수 있는 방향이 존재하지 않는다.)

    3개의 점이 남은 경우를 생각하겠습니다.

    .                |             .

         .           |      .

    3개의 점들 중 최소 2개는 좌나 우의 모양을 띄면서 연결 방향으로 이어질 수 있습니다.

    따라서 4의 시행을 소모합니다.

    + 아까와 같은 상황에서 점 하나를 추가해보자. 이때 이 점은 남은 두점과 각각의 오름, 내림을 가진다.

    1) 남은 두점보다 y좌표가 작은경우: 기존 마지막 점보다 작은 두 점이 이루는 오름-내림 관계에대한 연결방향이 가-이동방향과 반드시 겹치게된다.

    큰 경우도 마찬가지다.

    2) 남은 두점의 y좌표사이에 위치하는 경우: 이것도 1과 같은 풀이로 가능하다.

    (2 1 1 1 ..............  1 1 2 의수열으로 더한다는 것을 추론하였습니다)

    첫 번째 점은 당연히 2개의 시행을 소모하고 위의 모습과 같이 n-1개의 점은 n번의 시행을 소모합니다.

    (단 n=2의 경우 마지막 팩맨의 방향을 이용해서 하나의 시행만을 소모할 수 있다.)

    따라서 n<3 일때는 n+1, n>2 일때는 n+2 가 최솟값이 된다.

     

    설명이 더 필요한 부분은 설명하도록 하겠으니 검토 부탁드립니다...

    댓글 작성하기 좋아요0 댓글수0
  •  
    leesj Lv.5 2019.10.13
    확인요청중

    이미 풀린 문제이기는 하지만 문제가 되지 않는다면 풀이를 올리겠습니다.

    아래에 보이시다시피 x와 y가 겹치지 않게 놓는다면 어떤 모양이든 무조건

    k = n + 1(n < 3)

    k = n + 2(n >= 3)이 됩니다.

    댓글 작성하기 좋아요0 댓글수4
    •  
      leesj Lv.5 2019.10.13

      혹시 이미 해결된 문제는 더 이상 댓글을 쓰면 안 되나요?

      좋아요0
    •  
      뉴_턴 Lv.8 2019.10.13

      아니에요!! 이미 해결이 됬다고 해도 새로운 풀이 방법으로 풀면 올려도 상관이 없어요. 근데 문제를 푼 사람에는 첫번째가 아니라는 단점이랄까...요??

      좋아요0
    •  
      leesj Lv.5 2019.10.13

      아 그렇군요.

      좋아요0
    •  
      김우현 기자 Lv.4 2019.10.17

      뉴_턴 친구가 잘 말해줬네요!

       

      새로 올린 풀이는 출제자인 김홍녕 학생이 검토해 줄 예정입니다.

      홍녕 학생이 현재 입시로 정신이 없어 답변이 조금 늦어져도 이해해주세요!!

       

      좋아요0
  •  
    디듀우 Lv.6 2019.10.20

    매스펀에 응용문제를 출제했어요오!

    http://www.polymath.co.kr/mathfun/2510?page=1

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