글 읽기 - 이 코드가 틀린이유를 모르겠습니다. (풀이설명 있습니다.)

qktlf789456 3년 전 0

외판원순회 문제와 유사하다고 느꼈습니다.

dp 구조는

dp[구매했던인원BITMASK][현재갖고있는인원][이전에구매한가격] 이렇게 구조를 구성했습니다.

dp[a][b][c] >= 현재단계에서 소유했던 인원 수 일 경우에는 커트하였습니다.

틀린이유를모르겠네요!!

#include <iostream>

using namespace std;

int n;

char matrix[16][16]{ 0, };

int res = 1;

int dp[35000][16][10]{ 0, }; //bitmask, currently n's has, pre_value

void dfs(int pre_v, int cur_idx , int bitmask, int cur_cnt)
{
	res = res >= cur_cnt ? res : cur_cnt;

	if (dp[bitmask][cur_idx][pre_v] >= cur_cnt)
		return;

	dp[bitmask][cur_idx][pre_v] = cur_cnt;

	for (int i = 0; i < n; i++)
	{
		if ((bitmask & (1 << i)))
			continue;
		
		if (pre_v > matrix[cur_idx][i] - '0')
			continue;

		dfs(matrix[cur_idx][i] - '0', i, (bitmask | (1 << i)) , cur_cnt + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> matrix[i];

	dfs(matrix[0][0]-'0', 0,  1, 1);
	
	cout << res;

	return 0;
}

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

문제

문제

출처

ICPC

이 코드가 틀린이유를 모르겠습니다. (풀이설명 있습니다.)

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말