글 읽기 - 어디가 틀렸을까요..

fpnuseis 8년 전 0

dp개념 사용했고

dp 배열의 값이 갱신될때 이전 인덱스 값을 val이라는 배열에 저장해서

역추적이 되게 구현해보았습니다... 어디가 틀렸는지.. 아니면 힌트 좀 주시면 감사하겠습니다. ㅠㅠ

#include <stdio.h>

int val1[501];
int val2[501];

int dp[501][501];
int val[501];

int st[501];
int top=0;

int max(int a,int b){
	if(a>b) return a;
	else return b;
}

int main(){
	int n1,n2;
	scanf("%d",&n1);
	for(int i=0;i<n1;i++) scanf("%d",&val1[i]);
	scanf("%d",&n2);
	for(int i=0;i<n2;i++) scanf("%d",&val2[i]);
	for(int i=0;i<n1;i++) for(int j=0;j<n2;j++) if(val1[i]==val2[j]){
		dp[i][j] = 1;
	}

	for(int i=1;i<n1;i++){
		for(int j=0;j<n2;j++){
			if(val1[i]==val2[j]){
				for(int k=0;k<j;k++){
					if(val2[k]<val2[j]){
						if(dp[i][j]<dp[i][k]+1){
							val[j] = k;
							dp[i][j] = dp[i][k]+1;
						}
					}
				}
			}
			else dp[i][j] = dp[i-1][j];
		}
	}
	
	int res = 0;
	int pos=0;
	for(int i=0;i<n1;i++) for(int j=0;j<n2;j++) if(res<dp[i][j]){
		res = dp[i][j];
		pos = j;
	}
	printf("%d\n",res);
	
	
	int tmp = res;
	while(tmp>0){
		st[top] = val2[pos];
		top++;
		pos = val[pos];
		tmp-=1;
	}

	for(int i=top-1;i>=0;i--) printf("%d ",st[i]);
	printf("\n");
	return 0;
}

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

문제

문제

출처

ICPC

어디가 틀렸을까요..

fpnuseis 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말