[BOJ 14712 // C++] 넴모넴모 (Easy)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14712번 문제인 넴모넴모 (Easy)이다.
문제는 아래 링크를 확인하자.

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

14712번: 넴모넴모 (Easy)

주어지는 직사각형 격자판의 칸의 개수가 항상 25 이하이고 2^25는 3500만 미만이므로 모든 경우의 수를 적절히 탐색하는 것으로 문제를 해결할 수 있다.

 

넴모로 구성된 사각형 배치가 나오면 해당 방향의 탐색을 중단하고 이전 단계로 돌아가 탐색하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C;
int arr[26][26];

int ans = 0;
void func(int r, int c) {
	if (r > R) {
		ans++;
		return;
	}

	if (c < C) func(r, c + 1);
	else func(r + 1, 1);
	

	if (!(arr[r - 1][c - 1] && arr[r - 1][c] && arr[r][c - 1])) {
		arr[r][c] = 1;
		if (c < C) func(r, c + 1);
		else func(r + 1, 1);
		arr[r][c] = 0;
	}
}

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

	cin >> R >> C;
	
	func(1, 1);

	cout << ans;
}