Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

← Older revision		Revision as of 14:46, 26 March 2026
Line 12:		Line 12:
	using namespace std;		using namespace std;

	int arr[15][15] = {0,};		int arr[15][15] = {0,};
	int dp[15][10][1<<15] = {0,};		int dp[15][10][1<<15] = {0,};
	int N;		int N;

	int dfs(int num,int val, int visited){		int dfs(int num,int val, int visited){
	if(dp[num][val][visited]){		if(dp[num][val][visited]){
	if(dp[num][val][visited] == -1){		if(dp[num][val][visited] == -1){
	return 0;		return 0;
	}		}
	return dp[num][val][visited];		return dp[num][val][visited];
	}		}
	int maxn = 0;		int maxn = 0;
	for(int i = 0; i<N; i++){		for(int i = 0; i<N; i++){
	if(!(visited & (1<<i)) && arr[num][i] >= val){		if(!(visited & (1<<i)) && arr[num][i] >= val){
	maxn = max(maxn, dfs(i, arr[num][i], visited + (1<<i)) + 1);		maxn = max(maxn, dfs(i, arr[num][i], visited + (1<<i)) + 1);
	}		}
	}		}

	dp[num][val][visited] = maxn;		dp[num][val][visited] = maxn;
	if(dp[num][val][visited] == 0){		if(dp[num][val][visited] == 0){
	dp[num][val][visited] = -1;		dp[num][val][visited] = -1;
	return 0;		return 0;
	}		}
	return dp[num][val][visited];		return dp[num][val][visited];
	}		}

Line 42:		Line 42:
	for(int i = 0; i<N; i++){		for(int i = 0; i<N; i++){
	for(int j = 0; j<N; j++){		for(int j = 0; j<N; j++){
	scanf("%1d", &arr[i][j]);		scanf("%1d", &arr[i][j]);
	}		}
	}		}
Line 58:		Line 58:

	== 곽정흠 ==		== 곽정흠 ==

175.124.46.11: {CREATE}

2016-10-09T14:50:24Z

{CREATE}

New page

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/1648|그림 교환]
= 참가자 =
* 15이원준

= 코드 =
== 15이원준 ==
#include<iostream>
#include<algorithm>
using namespace std;

int arr[15][15] = {0,};
int dp[15][10][1<<15] = {0,};
int N;

int dfs(int num,int val, int visited){
if(dp[num][val][visited]){
if(dp[num][val][visited] == -1){
return 0;
}
return dp[num][val][visited];
}
int maxn = 0;
for(int i = 0; i<N; i++){
if(!(visited & (1<<i)) && arr[num][i] >= val){
maxn = max(maxn, dfs(i, arr[num][i], visited + (1<<i)) + 1);
}
}

dp[num][val][visited] = maxn;
if(dp[num][val][visited] == 0){
dp[num][val][visited] = -1;
return 0;
}
return dp[num][val][visited];
}

int main(){
cin>>N;
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
scanf("%1d", &arr[i][j]);
}
}
cout<<dfs(0,0,1) + 1<<endl;
}

== 박인서 ==

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==
*dfs로 최대값을 찾고 도중에 겹치는 것은 dp를 이용했습니다.
== 박인서 ==

== 곽정흠 ==

1R/2016 10 09 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

175.124.46.11: {CREATE}