4301. 콩 많이 심기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWLv-yZah48DFAVV&categoryId=AWLv-yZah48DFAVV&categoryType=CODE

SW Expert Academy

 

시간을 보고 DFS는 아니라고 생각해서 벡터랑 조건처리로 수행했는데 시간초과 발생.

생각해보니 벡터도 필요 없는 문제였다.

최대가 되려면 조금만 생각해보면 처음 인덱스부터 꽉꽉 채우면서 2거리에 있는 것만 비우면 되었기 때문에

배열로 visit처리 해주면서 상하좌우 2거리만 없으면 개수 +1 진행.

 

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;

int N, M;
bool arr[1000][1000];



int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> N >> M;
		int result = 0;
		memset(arr, 0, sizeof(arr));

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (!arr[i][j])
				{
					bool flag = false;
					if (i - 2 >= 0)
					{
						if (arr[i - 2][j])
						{
							flag = true;
						}
					}

					if (i + 2 < N)
					{
						if (arr[i + 2][j])
						{
							flag = true;
						}
					}

					if (j - 2 >= 0)
					{
						if (arr[i][j - 2])
						{
							flag = true;
						}
					}

					if (j + 2 < M)
					{
						if (arr[i][j + 2])
						{
							flag = true;
						}
					}

					if (!flag)
					{
						arr[i][j] = true;
						result++;
					}
				}
				
			}
		}

		cout << "#" << test_case << " " << result << endl;

		
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}