[백준] 23247번 Ten C++ 문제풀이

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

23247번: Ten

문제 풀이

맨 처음에 문제를 보자마자 누적합 배열을 만들어야하나 라고 생각했는데, 어떤식으로 풀어야 할지 모르겠어서 완전 탐색 방식으로 문제를 해결했다.

위의 그림처럼 생각해서 탐색하기로 하고 코드를 작성했다.

소스 코드

#include <iostream>
using namespace std;

int ic[301][301] = { 0 };
int result = 0;
int m, n;

void div_num(int row, int col, int rowcol, int num);

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> ic[i][j];
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			div_num(i, j, 1, ic[i][j]);
		}
	}

	cout << result << '\n';
}

void div_num(int row, int col, int rowcol, int num) {
	if (num == 10 && col + rowcol <= n && row + rowcol <= m) {
		result += 1;
		return;
	}
	else if (num > 10)
		return;

	// m에 관해서 탐색
	int cnt_1 = num;
	if (col + rowcol <= n) {
		for (int i = row + rowcol; i < m; i++) {
			for (int j = col; j < col + rowcol; j++) {
				cnt_1 += ic[i][j];
			}

			if (cnt_1 == 10) {
				result += 1;
			}
			else if (cnt_1 > 10)
				break;
		}
	}

	//n에 관해서 탐색
	int cnt_2 = num;
	if (row + rowcol <= m) {
		for (int i = col + rowcol; i < n; i++) {
			for (int j = row; j < row + rowcol; j++) {
				cnt_2 += ic[j][i];
			}

			if (cnt_2 == 10) {
				result += 1;
			}
			else if (cnt_2 > 10)
				break;
		}
	}

	//현재 n x n 행렬에서 (n+1) x (n+1)행렬로 늘린 다음에 다시 탐색 
	int next_num = num;
	if (row + rowcol + 1 < m || col + rowcol + 1 < n) {
		for (int i = row; i < row + rowcol; i++) {
			next_num += ic[i][col + rowcol];
		}
		for (int j = col; j < col + rowcol; j++) {
			next_num += ic[row + rowcol][j];
		}
		next_num += ic[row + rowcol][col + rowcol];
		div_num(row, col, rowcol + 1, next_num);
	}
	else
		return;
}