https://www.acmicpc.net/problem/1783
시간 제한 | 메모리 제한 | solved.ac 티어 |
2초 | 128MB | 실버 4 |
문제
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.
입력
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.
이 문제가 특이한 것은 오로지 오른쪽으로만 움직인다는 점이다. 따라서 움직임은 다음과 같다.
우선 세로(n)가 1이라면 나이트는 움직일 수 없기 때문에 본인이 처음에 위치한 좌하단 단 한칸만을 여행한 셈이 된다. 따라서 이때는 1이다.
세로가 2라면, 나이트는 2, 3번의 방법으로만 움직일 수 있다. 하지만 이동 횟수가 4 이상이라면 1번과 4번의 움직임도 같이 해야 하지만, 1, 3번 방법은 세로의 길이가 3 이상이어야 하기 때문에 더 이상 움직일 수 없다.
따라서 이러한 경우에는 가로가 아무리 길어도 최대 4칸밖에 움직일 수 없다. 하지만 이때의 가로가 7보다 작은 경우 어떻게 해야 할까? 1부터 시작하여 2, 3번의 움직임은 가로 2칸을 움직이기 때문에 (가로의 길이 + 1) / 2가 곧 칸의 개수이다. 등차수열을 배우면 당연한 이야기일 것이다.
그렇다면 세로가 3 이상인 경우를 보자. 이때는 1, 4번의 움직이는 방법도 사용할 수 있다. 그렇다면 m을 고려하지 않고 최대한 많은 칸을 이동하려면 어떻게 움직여야 할까? 병든 나이트는 오른쪽으로만 움직이고, m자체는 정해져 있기 때문에 오른쪽으로 덜 이동하는 1, 4번의 방법을 최대한 많이 써야 할 것이다. 하지만 4번 이상 움직이는 경우, 2, 3번 방법도 각각 한번 이상 써야하기 때문에 2, 3번 방법을 단 한번씩만 사용한 후에, 1, 4번을 계속해서 사용하면 될 것이다. 그렇기 때문에 가로로 움직이는 길이가 1씩 더 큰 2, 3번의 움직임으로 인해 총 (가로(m) - 2) 만큼의 칸을 여행할 수 있다.
하지만 여기서도 예외가 발생한다. 1, 2, 3, 4번의 움직임을 한번씩 사용하면 총 6칸(2+2+1+1)을 가로방향으로 움직이는데, 이때 주어진 가로의 길이가 7보다 작다면 어떻게 해야 하나? 이때의 경우, 여행 가능한 칸의 최댓값은 4이다.
#include <bits/stdc++.h>
using namespace std;
int main () {
// fast i/o
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// n = 세로, m = 가로
int n, m;
cin >> n >> m;
if (n == 1) cout << 1;
else if (n == 2) cout << min(4, (m + 1) / 2);
else if (m < 7) cout << min(4, m);
else cout << m - 2;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 1021번 C++ 풀이 (0) | 2022.03.09 |
---|---|
백준 2309번 C++ 풀이 (0) | 2022.03.08 |
백준 1080번 C++ 풀이 (0) | 2022.03.07 |
백준 4949번 C++ 풀이 (0) | 2022.02.26 |
백준 9659번 C++ 풀이 (0) | 2022.02.16 |