글 읽기 - [java] 대부분의 반례를 찾아보았는데 어느부분이 틀리는지 모르겠습니다

soon0799 2년 전 0

조금 지저분 하게 하긴했는데 저는 union 배열과 stack을 이용했습니다.

union 같은 경우에는 각 바로 앞에 어떤수가 왔었는지 그 수에대한 index 넘버를 저장하였고

ex)arr = {20,30,10, 15, 20,50, 30, 35, 60} 인 경우 union={-1,0,-1,2,3,4,4,6,7,-1} 같은 방식으로 들어갑니다.

그래서 최대 값이 나오는 index를 찾고 거기서 역방향으로 추적해서 stack에 넣어 후입 선출을 이용해 출력했습니다.

갯수같은 경우에는 stack에 추가될때마다 ++해줬구요 근데 뭐가 틀린지를 잘 모르겠습니다

문제를 잘못이해했네요 다 더했을때 가장 큰 값이 나오는걸로 했는데 그냥 길이가 가장 길게 만드는 거네요

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n=sc.nextInt();
		int[] arr= new int[n];
		int[] dp = new int[n];
		int[] union = new int[n];
		Stack<Integer> index= new Stack<Integer>();
		int max=0;
		int indexofmax=0;
		for(int i=0;i<n;i++) {
			arr[i]=dp[i]=sc.nextInt();
			union[i]=-1;
		}

		for(int i=0;i<n;i++) {
			for(int j=0;j<i;j++) {
				if(arr[j]<arr[i]) {
					if(dp[i]<dp[j]+arr[i]) {
						dp[i]=dp[j]+arr[i];
						union[i]=j;
					}

				}
			}
		}

		for(int i=0;i<n;i++) {
			if(dp[i]>max)max=dp[i];
		}
		for(int i=0;i<n;i++) {
			if(dp[i]==max)indexofmax=i;
		}
		int cnt=0;
		while(true) {
			cnt++;
			index.add(indexofmax);
			indexofmax=union[indexofmax];
			if(indexofmax==-1) {
				break;
			}
		}
		System.out.println(cnt);
		while(!index.isEmpty()) {
			System.out.print(arr[index.pop()]+" ");
		}
		
	}
}

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

문제

문제

출처

ICPC

[java] 대부분의 반례를 찾아보았는데 어느부분이 틀리는지 모르겠습니다

soon0799 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말