글 읽기 - 도와주세요!!ㅠㅠ

his130 6년 전 0

대각선을 나누고, 대각선을 점프하면서 구현했습니다.

근데 여전히 시간초과가 발생하는데 어떤 문제일까요??

#include<iostream>

using namespace std;
int n, ans;
int map[10][10];
bool chk[19];

void dfs(int k, int sum)
{
	//오른쪽 상단 ↗ 대각선이 종료
	if (k == 2 * n - 1)
	{
		if (sum > ans)
		{
			ans = sum;
		}
		return;
	}
	
	//오른쪽 상단 방향 ↗ 대각선의 첫번째 x,y값
	int x = k;
	if (x >= n)
	{
		x = n - 1;
	}
	int y = k - x;
	
	for (int i = 0; i < n; i++)
	{
		int nx = x - 1*i;
		int ny = y + 1*i;
		int c = ny - nx + n - 1;	//nx,ny의 오른쪽 하단 방향 ↘ 대각선의 index
		if (nx >= 0 && ny >= 0 && nx < n && ny < n)
		{
			if (map[nx][ny] == 1 && !chk[c])
			{
				//오른쪽 하단 방향 대각선 ↘ 사용여부 체크.
				chk[c] = true;
				dfs(k + 1, sum + 1);
				chk[c] = false;
			}
		}
		//범위 벗어나면 for문을 그냥 벗어나도록
		else
		{
			break;
		}
	}
	//오른쪽 상단 방향 대각선 ↗ 에서 아무것도 선택안하고, 다음 대각선으로 넘어감.
	dfs(k + 1, sum);
}
int main()
{
	freopen("input.txt", "r", stdin);

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
		}
	}

	dfs(0, 0);

	cout << ans << "\n";

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도와주세요!!ㅠㅠ

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말