고집센 개구리

고집센 개구리

아이가 아푸다. 나도 기분이 매우 다운된다. 게다가 잘 먹던 약도 안먹는다. 약을 안먹으니 열이 엄청나게 올라가고 있다.힘들다. 어째거나…오늘 아는 형님이 문제 하나를 보여줬는데 거기에 양교수님 성함이 들어있었다. 찾아 뵙지도 못하고 송구하기만 하다. 근데 문제가 은근히 재미있었다.
내 수준이 낮으니 재미있었다가 맞겠다.

일단 문제부터 보자.

문제

• 두 개구리 가족이 징검다리를 건너다 돌 하나를 사이에 두고 서로 마주쳤다.
  좁은 징검다리여서 한 가족이 뒤로 돌아 나와서 비켜주어야 지나갈 수 있지만
  개구리들은 고집이 세어서 서로 비켜주려하지 않는다.
• 어느 개구리도 뒤로 돌아가지 않고 가던 길을 계속 갈 수 있도록 하려면 어떻게 해야 하는가?

목표

• 최소의 움직임으로 왼쪽에 서 있던 개구리들을 오른쪽으로, 오른쪽에 있던 개구리들을 오른쪽으로 옮긴다.

  왼개굴1 왼개굴2 왼개굴3 빈칸 오른개굴1 오른개굴2 오른개굴3

뭐 이런상태다

규칙

• 모든 개구리들은 돌 위에 서 있어야 한다.
• 왼쪽에 있는 개구리는 오른쪽으로만, 오른쪽에 있는 개구리들은 왼쪽으로만 이동
• 한 개구리 뒤에 빈 돌이 있으면, 그 개구리를 넘어 갈 수 있다.
• 한 번에 한 개구리만 돌 하나만큼 움직일 수 있다.

뭐 이런 문제이다. 약간 헷갈릴 수 있는데 왼쪽 개구리를 L 오른쪽 개구리를 R빈칸을 0이라 해보자. 그렇다면 다음과 같이 표현될 수 있다.

L L L 0 R R R 뭐 이런 상태인거지.

그럼 이런 이동이 가능하다는 거다

L L L R 0 R R (R 개구리가 왼쪽으로 이동)

L L L R R 0 R (R 개구리가 쩜뿌. 물론 이렇게 이동하면 다음 이동이 불가능)

뭐 이런거 이다. 이를 해결하기 위해서 머리를 굴리다보니.. 당연히 움직여야 할 개구리가 정해진다는 것이고. 손으로 풀다보면 규칙이 보인다.

그 규칙은 이렇게 생각했다.

목표

일단 L R L R L R 의 형태가 반드시 되어야 한다.
만약 양 끝단이 아닌 곳에서 RR 혹은 LL 의 형태가 나타나면 망하는 것이다.
1. LRLRLRLR의 형태로 배치하고
2. RRRR LLLL의 형태로 만들어 나간다.

간단하다.

그렇다면 1번을 목표로 생각해 보자

L 0 R 의 상태라면 누구든지 움직일 수 있다. 우리는 편의상 R을 처음 움직이자. 

그렇다면 다음과 같이 움직일 수 있다.

L R 0 (1회 움직임)

그런데 만약 각각의 개구리가 더 있다고 가정해 보자

L L 0 R R 의 상태에서 R을 처음 움직이면 다음과 같이 배열된다.

L L R 0 R (1회 움직임)

그리고 나서 살펴보면 더 이상 R을 움직일 수 없다는 결론을 얻을 수 있다. 그렇다면 턴을 L로 넘기자 L을 움직이는 방법은

L 0 R L R (1회 움직임)

0 L R L R (2회 움직임)

L은 2회 움직일 수 있었으며 우리의 목표인 1번을 도달했다. 만약 3쌍짜리였다면 어떻게 되었을지 생각해보면 의외로 간단히 생각할 수 있는데 지금의 상태에서 양 끝에 L과 R을 붙이면 된다.

L 0 L R L R R

이 상태에며 L을 더 이상 움직이면 망하다는 것을 알 수 있다. 머리가 더 비상하다면 R을 이제 움직일 것이라는 것을 알 수 있으며, R은 3번 움직일 것이라 예상할 수 있다.
움직여 볼까?

L R L 0 L R R (1회 움직임)

L R L R L 0 R (2회 움직임)

L R L R L R 0 (3회 움직임)

그렇다면 우리의 목표 1번을 달성하기 위해서는 1+2+3+4+5….n회가 필요함을 알 수 있다.

그리고 2번 목표를 생각해 보자

L R L R L R 0 에서 L들을 움직이면 된다. 몇 번? 3번이다(n번) 이를 움직이면 다음과 같아 진다.

0 R L R L R L

이 상태에서 나는 꼭 2번만 움직이고 싶었다. 그런데 R을 3번 움직여야 하더라.. 그럼 생각을 고쳐먹고 이렇게 바꾸지

R 0 L R L R L 이렇게 하고 나면, R을 2번만 움직이면 된다(n-1)회

R R L 0 L R L (1회)

R R L R L 0 L (2회) 이상태에서 나는 1번만 움직이고 싶어졌다. 그래서 이렇게 바꾸고 생각한다.

R R L R 0 L L 그러면 L을 한번만 움직이면 된다.

R R 0 R L L L 우하하하… 그리고 안움직이고 싶었다. 그래서 R을 그냥 한번 움직인다.

R R R 0 L L L 이렇게 된다.

그렇다면 다시 목표 2를 위해서는 1 + 2+ 3+ 4+5+…n회에 꼼수 n번이 있었다.

결론 최후에는

시그마(웹에서는 시그마 어케 하는겨?) k = n*(n+1)/2 인데 이게 2개가 있으므로

n*n + n 에 꼼수 n을 더하면

결론 : n(n+2) 이 된다.

이하 소스코드이다.

#include <iostream>
#include <cstdio>

using namespace std;
int ar[10000];
void printfall(int n){
    cout<<"\nprint all data\n";
    for(int i=1;i<n*2+2;i++){
        cout<<ar[i]<<" ";
    }
    cout<<"\n";
}
//   3    3   2  1   1
//  m-2  m-1  m m+1 m+2
void generater(int n){
    int i;
    for(i=1;i<=n;i++){
        ar[i]=3;
    }
    ar[i]=2;
    for(++i;i<=2*n+1;i++){
        ar[i]=1;
    }
    ar[i]=3;
    ar[0]=1;
}




int main()
{
    int n=3; //몇쌍짜리 인가?

    cin>>n;
    generater(n);//일단 만들어라.

    int m=n+1; //가운데는 어디잉가?
    int di=1;//어디 방향부터 갈 것이냐?
    int cnt=0;
    int k=0;

    //이 녀석은 일단 31313131 혹은 1313131 의 형식으로 몰아버리는 녀석이다.
    for(int i=1;i<=n;i++){
        //i번 움직여야 한다.
        k = i;
        while(k--){
            if(ar[m-1]!=ar[m+1]){
                swap(ar[m],ar[m+di]);
                m=m+di;
                cnt++;
            }
            else
            {
                swap(ar[m],ar[m+(di*2)]);
                m=m+(di*2);
                cnt++;
            }
        }
        di*=-1;
    }
    //이녀석은 각 방향으로 돌아가면서 갈 수 있는 녀석들을 정리하는 녀석이다.
    for(int i=n;i>0;i--){
        k=i;
        while(k--){
            swap(ar[m+di*2],ar[m]);
            m=m+di*2;
            cnt++;
        }
        di*=-1;
        swap(ar[m+di],ar[m]);
        m=m+di;
        cnt++;
    }
    cout<<"cnt : "<<cnt<<"\n";
    printfall(n);


    return 0;
}