서대문구에 있는 한 연못에 N마리의 하얀 개구리와 N마리의 검은 개구리가 2N+1개의 연꽃으로 이루어진 징검다리를 건너려고 하고 있다. 그림에서 보이는 것과 같이 각 무리의 개구리들에는 앞에서부터 1부터 N까지 번호가 붙어있다. 각 무리의 개구리들은 징검다리를 건너서 서로 반대쪽으로 지나가려고 하고 있다. 그러나 바쁜 일이 있는 개구리들은 서로 먼저 지나가라고 양보하기 어려운 상황이었기 때문에 모두 동시에 징검다리를 건너려고 한다.
개구리들은 다음과 같이 이동할 수 있다.
하얀 개구리들은 오른쪽으로만, 검은 개구리들은 왼쪽으로만 움직인다.
한 번에 한 마리의 개구리만 움직일 수 있다.
자신의 진행 방향 바로 앞에 있는 연꽃이 비어있는 경우, 진행 방향으로 한 칸 이동할 수 있다.
자신의 진행 방향 바로 앞에 있는 연꽃에 자신의 색과 다른 개구리가 있는 경우, 그 개구리 한 마리를 건너뛰어서 두 칸 이동할 수 있다.
자신의 진행 방향 앞에 있는 두 개 이상의 연꽃이 비어있다고 하더라도 한 번에 두 칸 이상 이동할 수 없다.
두 마리 이상의 개구리를 뛰어넘거나, 자신의 색과 같은 색의 개구리를 뛰어넘을 수 없다.
위의 규칙에 따라 각 개구리를 움직여서 그림과 같이 개구리들이 반대편에 도달할 수 있도록 하여라.
첫 번째 줄에 개구리들을 움직여야 하는 횟수 M을 출력한다. 단, M은 1,500,000을 넘어서는 안된다.
두 번째 줄부터 M개의 줄에 걸쳐서 움직인 개구리의 정보를 순서대로 출력한다. p번째 하얀 개구리가 움직인 경우 1 p를 출력하고, p번째 검은 개구리가 움직인 경우 2 p를 출력한다.
입력 예시
1
출력 예시
3
1 1
2 1
1 1
풀이
브루트포스로 테스팅하고 싶을테지만... 그럴 필요는 없다.
재귀적으로, 맨 처음에는 다음과 같은 상황이 가능하다.
처음은 흰색(검은색이여도 상관없다) 개구리 1번이 1칸 움직인다.
이전에 다른 색 개구리가 N번까지 움직였다고 가정하자. 그렇다면 다른 색 N번째 개구리의 칸 뒤쪽(진행 방향 반대)은 비어있을 것이고, 현재 색 1번 개구리는 N번 개구리를 뛰어넘어 그 칸에 도달할 수 있다. 현재 색 2번 개구리는 1번 개구리가 움직이면서 발생한 빈 칸에 도달할 수 있다. 이런 식으로 진행하면, 현재 색 개구리는 N+1번 개구리까지 움직일 수 있게 된다.
즉 1 ~ N번까지, 1 ~ i번째 개구리를 이동하는 것이 포인트이다. 총 횟수는 N*(N+1) / 2이다.
그리고 N번째 개구리가 모두 이동했다면, N번째 개구리와 다른 색의 1번째 개구리부터 N번째 개구리가 이동 가능하다. 이동 횟수는 N이다.
이제부터는 반대로 적용된다. 1 ~ N번까지, i ~ N번째 개구리를 이동시킨다. i번째 이하 개구리는 배치가 끝난 상황이기 때문이다. 이동 횟수는 N*(N+1)/2이다.
따라서 최적의 이동 횟수는 N^2 + 2*N이며, 앞선 알고리즘에 따라 차례대로 출력을 진행하면 된다(줄글로 쓰니 어려워 보이는데, 실제로 그림을 그려가면 직관적으로 이해가 쉽다. 개구리를 N=2, N=3일때 직접 옮겨보도록 하자)
풀이 코드
N = int(input())
print(N**2 + 2*N)
cnt = 0
for i in range(1, N+1) :
for j in range(1, i+1) :
print(cnt+1, j)
cnt = 1-cnt
for i in range(1, N+1) :
print(cnt+1, i)
cnt = 1-cnt
for i in range(1, N+1) :
for j in range(i, N+1) :
print(cnt+1, j)
cnt = 1-cnt
