[백준 14557] Memory (C++)

https://www.acmicpc.net/problem/14557

문제

---

모래두지는 어디를 가나 R×C장의 카드를 들고 다닌다. 이 카드들에는, 같은 무늬가 그려진 카드가 정확히 두 장 씩 있다.  카드를 들고 다니는 이유는, 혼자 있을 때 짝 맞추기 게임을 하기 위해서이다. 게임은 다음과 같은 방법으로 진행된다.

1. 처음에 카드를 잘 섞은 후 가로 R행, 세로 C열로 카드들을 무늬가 보이지 않게 뒷면으로 잘 배치한다.
2. 다음의 행동을 카드가 모두 없어질 때 까지 반복한다.
   1. 카드를 한 장 정해 뒤집어서 무늬를 본다.
   2. 나머지 카드를 한 장 정해 뒤집어서 무늬를 본다.
   3. 두 카드에 그려진 무늬가 같으면, 카드를 두 장 모두 게임에서 제외시킨다. 아니면, 다시 원래대로 뒷면으로 뒤집어 놓는다.
3. 게임에서 승리한다!

모래두지는, 행동을 될 수 있는 한 적게 사용해서 게임에서 승리하려고 한다. 그는 행동의 수를 줄이기 위해 최적의 전략을 쓸 것이다. 이때, 게임에서 승리하기 위한 최소의 행동 횟수와, 최대의 행동 횟수를 구하여라. 

 

입력

---

첫째 줄에 정수 R,C가 공백으로 구분되어 들어온다. (1 ≤ R,C ≤ 10, R×C는 2의 배수.)

출력

---

게임에서 승리하기 위한 최소의 행동 횟수와, 최대의 행동 횟수를 공백으로 구분하여 출력하여라.

 

문제 풀이

---

수학 문제.

 

카드는 R*C 장이고, 모두 같은 무늬가 그려진 한 쌍의 카드로 만들 수 있다. 따라서 R*C / 2 쌍이 존재하고, 아주 운이 좋다면 모두 한번에 같은 무늬를 선택하여 게임을 끝낼 수 있다. 즉, 이것이 최소 행동 횟수가 된다.

아주 운이 안좋은 경우는 최대 행동 횟수가 된다. 한 쌍의 카드의 무늬가 밝혀져야 카드를 뒤집어 없앨 수 있으므로 적어도 R*C/2번 행동이 필요하고, 짝을 맞추기 이전에 카드가 모두 없어지지 않을 때가 된다. 짝을 맞추기 이전에 카드가 모두 없어지지 않는 횡동의 횟수는 (R*C / 2) - 1가 된다. 이만큼 행동을 했을 때 모든 카드의 무늬가 밝혀진다. 따라서 최대 행동 횟수는 R*C-1가 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int R, C;
	cin >> R >> C;
	long long minAnswer = R * C / 2;
	long long maxAnswer = R * C - 1;
	cout << minAnswer << " " << maxAnswer << "\n";
	return 0;
}