알고리즘(C++) / 백준 1783 : 병든 나이트

1783

www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

 

 

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

 

 

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

 

 

코드

//1783 병든 나이트
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;

	if (N == 1) {
		cout << "1" << endl;
	}
	else if (N == 2) {
		if ((M + 1) / 2 <= 4)
			cout << (M + 1) / 2 << endl;
		else
			cout << "4" << endl;
	}
	else {
		if (M < 7) {
			cout << min(4, M) << endl;
		}
		else
			cout << M - 2 << endl;
	}
	return 0;
}

 

설명

• N이 1인 경우
• N이 2인 경우
• N이 3이상인 경우

로 나눠서 문제를 풀 수 있다. 

병든 나이트는 오른쪽으로만 이동할 수 있고, 왼쪽으로는 이동하지 못한다. 따라서 칸의 최대 개수를 구하기 위해서는 오른쪽의 이동을 최소로만 해야 한다. 열(세로)에 아무리 많아도 한 번 밖에 존재를 하지 못한다. 따라서 M의 크기에 영향을 많이 미친다. 

 

N이 1인 경우에는 움직일 수 없으므로 방문할 수 있는 칸이 시작 지점인 한 칸만 존재한다.

★

 

N이 2인 경우에는 2번조건과 3번 조건만 반복할 수 있다. 그런데 1,2,3,4 조건을 모두 사용하지는 못하기 때문에 4번 이상 이동을 하지 못한다. M이 7 이상일 때 칸의 최대 개수는 4개이다. 

		★				★
★				★

 

N이 3이상인 경우에는 M이 7 이상인 경우와 7 미만인 경우와 나눠서 생각해볼 수 있다.

• M이 7 미만인 경우

	★		★
★		★

M이 7 미만인 경우에는 1, 2, 3, 4 조건을 모두 사용하지 못하기 때문에 4번 이상 이동을 하지 못한다. 따라서 M 칸수만큼 출력하는데 M이 4 이상일 때는 더 이상 이동하지 못하므로 4를 출력한다.

 

• M이 7 이상인 경우

	★				★		★		★
			★
★						★		★

M이 7이상인 경우 7칸까지는 1,2,3,4 조건을 모두 사용하여 이동할 수 있다. 그 이후는 오른쪽으로 한 칸씩만 이동하는 조건인 1번과 4번 조건만으로 이동하여 칸의 최대 개수를 구할 수 있다.

따라서 M-2을 출력할 수 있다. 

 

결과

 

고찰

이번 문제는 문제에 대한 설명이 많지 않고 문제를 잘못 이해해서 문제 푸는 데에 시간이 많이 걸렸다. 

체스판의 크기 N과 M을 입력받고 방문할 수 있는 모든 칸의 개수를 출력하는 줄 알았지만, 이동하는 루트는 한 가지 루트이고 도착 지점에서만 다른 칸으로 움직일 수 있었다. 

또한, 1번부터 4번까지의 조건을 한 번씩 움직이지 않았더라면 다른 움직임을 할 수 없다는 것이다. 즉, 1번과 2번 조건만으로 4번을 움직이게 되고, 3번 4번 조건으로만 움직여야 하는데 그럴 수 없다면 이동을 하지 못한다.

문제가 약간 애매하게 작성되어서 다른 사람들이 작성한 코드와 설명을 보고 이해할 수 있었다.

문제가 그렇게 좋은 문제는 아닌거 같다...