글 읽기 - 알고리즘에 오류가 있을까요??

sksdong1 7년 전 1

일단 문제를 제가 해석하기로

자동차 크기가 숫자로 주어졌을 때,

들어오는 순서에 따라 커지는 순에서 작아지는 순으로 나열해야하며, 차를 선택하지 않을수 있다.

각각의 차는 맨앞에 넣거나, 맨뒤에 넣을 수 있다.

이정도 조건이고 제 알고리즘은 어떤 차를 기준으로 앞에 쌓이려면 무게가 커야하고, 뒤에 쌓이려면 무게가 작아야하기 때문에

각각의 차를 기준으로 최장 증가수열, 최장 감소 수열을 구해서

기준 차에대해서 증가수열만큼 앞에 쌓고, 감소 수열만큼 뒤에 쌓아서 가장 긴 값이 답이 될 거라고 생각했는데 60~70%에서 틀리네요

머가 문제일까요?? 아니면 TC좀 알려주세요~

import java.util.Arrays;
import java.util.Scanner;

class Main{
	
	int n,a[],dp[],dp2[];
	Scanner sc = new Scanner(System.in);
	void main(){
		n = sc.nextInt();
		a = new int[n+1];
		dp = new int[n+1];
		dp2 = new int[n+1];
		a[0]=-1;
		for(int i=1;i<=n;i++) a[i] = sc.nextInt();
		Arrays.fill(dp,-1);
		Arrays.fill(dp2,-1);
		lis(0);
		a[0]=987654321;
		lis2(0);
		
		int ret = -1;
		for(int i=1;i<=n;i++){
			ret = max(ret,dp[i]+dp2[i]-1);
		}
		System.out.println(ret);
	}
	int lis(int here){
		if(here==n) return dp[here] = 1;
		
		int ret = dp[here];
		if(ret!=-1) return ret;
		ret=1;
		
		for(int next=here+1;next<=n;++next){
			if(a[here]<a[next]){
				ret = max(ret,lis(next)+1);
			}
		}
		return dp[here] = ret;
	}
	int lis2(int here){
		if(here==n) return dp2[here] = 1;
		int ret = dp2[here];
		if(ret!=-1) return ret;
		ret=1;
		
		for(int next=here+1;next<=n;++next){
			if(a[here]>a[next]){
				ret = max(ret,lis2(next)+1);
			}
		}
		return dp2[here] = ret;
	}
	int max(int a,int b){
		return a>b?a:b;
	}
	public static void main(String[] args) {
		new Main().main();
	}
}

kthng 7년 전 1

안녕하세요 ㅋㅋㅋㅋ

여기서 보다니 엄청 반갑습니다!

저도 lis lds두개로 풀어서 알고리즘은 맞는것 같아요.

도와주려고 필사적으로 코드를 들여다봤는데

답이랑 관련 있을까 싶지만

dp, dp2가 -1인 상태로 남아있을 수도 있을 것 같네요

만약 5 4 3 2 1의 경우에는 dp[1] ~dp[5] 모두 1이어야 하지만 dp[2]~dp[5]는 -1인 채로 남아있을 것 같아요.

for(int i=1;i<=n;i++){
ret = max(ret,dp[i]+dp2[i]-1);
}

이부분만 만져주면 될 듯 합니다!

sksdong1 7년 전 1

코드 봐주셔서 감사합니다..

근데 위에서 말씀하신 경우는 dp[2]~dp[5]까지 1이 되용..

각각 배열의 0번 인덱스에 lis에서는 0 , lds 는 큰 값을 넣어서 lis 함수에서 here가 0일 때 모든 인덱스를 호출해서 1씩은 저장이 됩니다.

위랑 비슷한 알고리즘으로 푸셨다니 좀 더 생각해봐야겠네용.

kthng 7년 전 0

그렇네요.. 도움이 되고싶었는데ㅜㅜ

화이팅입니다~!

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

문제

문제

출처

ICPC

알고리즘에 오류가 있을까요??

sksdong1 7년 전 1

kthng 7년 전 1

sksdong1 7년 전 1

kthng 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말