3548 : Connect3
- 제한시간
- 1000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 8 회
- 시도횟수
- 17 회
문제
Connect3은 잘 알려진 게임 중 하나인 Connect4를 단순화시킨 게임이다. Connect3는 2명이 하는 게임으로, 한 명은 검은 돌을, 나머지 한 명은 흰 돌을 4x4 크기의 격자판에 놓으면서 게임을 진행한다. 왼쪽 아래 격자의 좌표를 (1, 1), 오른쪽 위 격자의 좌표를 (4, 4)라고 하자. 각 플레이어는 격자의 열을 하나 선택한 뒤, 비어있는 가장 낮은 칸에 돌을 위치시킨다. 예를 들어, (3, 1)에 돌이 놓이기 위해서는 (1, 1), (2, 1)에 돌이 이미 있어야 한다. 게임은 3개의 흰색, 혹은 검은색 돌이 수평, 수직, 혹은 대각선으로 연속해 있을 때 게임이 끝나며, 그 돌을 놓은 사람이 승리한다. 게임이 끝난 이후에는 더 이상 돌을 놓을 수 없다.
(4, 1) (4, 2) (4, 3) (4, 4)
(3, 1) (3, 2) (3, 3) (3, 4)
(2, 1) (2, 2) (2, 3) (2, 4)
(1, 1) (1, 2) (1, 3) (1, 4)
상수는 위와 같은 조건을 만족하도록 게임을 했을 때, 나올 수 있는 최종 게임판들 중 아래 조건을 만족하는 게임판들의 가짓수가 궁금했다: “게임이 가장 처음에 검은색 돌을 (1, x)에 놓으면서 시작했고, 가장 마지막 돌이 흰색이면서 (a, b)에 놓여지면서 게임이 끝난다.” 상수를 도와 게임판의 가짓수를 구해주자. 여기서 돌이 놓인 순서는 중요하지 않다는 것에 유의하자.
입력형식
첫 번째 줄에 첫 번째 돌이 떨어지는 열 위치 x를 의미하는 수 x가 주어진다. 두 번째 줄에 가장 마지막 돌이 떨어진 좌표 (a, b)를 의미하는 수 a, b가 주어진다.
출력형식
문제의 답을 첫 번째 줄에 수 하나로 출력한다.
입력 예복사하기 2 2 3 |
출력 예복사하기 516 |
입력 예복사하기 3 4 4 |
출력 예복사하기 177 |