2024. 6. 13. 00:59ㆍIT/BaekJoon
문제 링크
https://www.acmicpc.net/problem/1783
문제
병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.
- 2칸 위로, 1칸 오른쪽
- 1칸 위로, 2칸 오른쪽
- 1칸 아래로, 2칸 오른쪽
- 2칸 아래로, 1칸 오른쪽
병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.
체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.
입력
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
출력
병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.
통과한 답안
namespace _1783
{
internal class Program
{
static void Main(string[] args)
{
string[] inputs = Console.ReadLine().Split(' ');
int N = int.Parse(inputs[0]); // 세로
int M = int.Parse(inputs[1]); // 가로
int maxMoves = 0;
if (N == 1)
{
maxMoves = 1;
}
else if (N == 2)
{
maxMoves = Math.Min(4, (M + 1) / 2);
}
else
{
if (M < 7)
{
maxMoves = Math.Min(4, M);
}
else
{
maxMoves = M - 2;
}
}
Console.WriteLine(maxMoves);
}
}
}
(1, 1)에서 출발하는 나이트가 4가지 방법(↑2→1, ↑1→2, ↓1→2, ↓2→1)으로 이동할 수 있을 때,
N X M 크기의 체스판에서 가장 많이 방문하는 점의 개수를 찾는 문제이다.
단, 이동 횟수가 4회 이상이라면 이동 방법을 모두 1번씩 사용해야 한다는 조건이 있다.
이 문제를 해결하기 위해서 모든 경우를 탐색하는 방법이 아닌
크기에 따라서 이동할 수 있는 경우를 나눠서 해결하는 방법을 사용해야 한다.
1. 세로의 길이가 1인 경우
세로의 길이가 1이라면 나이트는 이동할 수 없으므로 칸의 수는 1이다.
2. 세로의 길이가 2인 경우
세로의 경우가 2라면 나이트는 (2, 1) 혹은 (-2, 1)로만 이동할 수 있으므로
가로의 길이 M에 따라서 최대 이동 칸 수는 달라지는데,
4(이동 횟수가 4회 이상이라면 (1, 2)와 (-1, 2)도 사용해야 하므로)와
M / 2(2칸씩 이동하므로) 중 작은 값이다.
3. 가로 길이가 7미만인 경우
가로가 짧아서 모든 이동 방법을 사용할 수 없으므로,
오른쪽으로 이동할 수 있는 칸 수를 계산한다.
따라서 4와 M 중 작은 값이다.
4. 그 외의 경우
모든 이동 방법을 사용할 수 있으므로 M에 따라서 칸이 많아지는데,
최소 2번은 오른쪽으로 2칸을 가야하므로, M - 2칸이 최대이다.
따라서 위의 경우들을 if문을 이용하여 나눠서 작성하였다.
'IT > BaekJoon' 카테고리의 다른 글
[BAEKJOON] 백준 19947: 투자의 귀재 배주형 (C#) (0) | 2024.06.14 |
---|---|
[BAEKJOON] 백준 6438: Reverse Text (C#) (0) | 2024.06.14 |
[BAEKJOON] 백준 22015: 金平糖 (Konpeito) (C#) (0) | 2024.06.12 |
[BAEKJOON] 백준 17175: 피보나치는 지겨웡~ (C#) (0) | 2024.06.10 |
[BAEKJOON] 백준 9711: 피보나치 (C#) (0) | 2024.06.10 |