글 읽기 - 11054번 반례 있나요? 게시판에 있는 반례 해봤는데 다 제대로 됩니다

aka2344 4년 전 0

게시판에 있는 반례들 모두 다 해봤고 다 잘 돌아가던데 왜 안되는지 모르겠습니다;

알고리즘은 LIS 활용해서 시작부터 K까지 LIS중 최대 길이와 K부터 N까지 LIS(역순)중 최대 길이를 합해서

따로 배열에 저장하고, [1 2 2 1]이나 [1 2 3 1 3 2 1] 처럼 중복되는 부분도 고려하여서 문제를 풀었는데 왜 안되는지 모르겠습니다,,

반례가 있을까요?

import java.util.*;
import java.util.stream.*;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] A = new int[n + 1];
		int[] B = new int[n + 1];
		int[] C = new int[n + 1];
		int[] D = new int[n + 1];
		int[] E = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			A[i] = sc.nextInt();
			C[n + 1 - i] = A[i];
		}
		for (int i = 1; i <= n; i++) {
			int max = -1;
			for (int j = 0; j <= i; j++) {
				if (A[j] < A[i]) {
					if (B[j] > max) {
						max = B[j];
						B[i] = B[j] + 1;
					}
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			int max = -1;
			for (int j = 0; j <= i; j++) {
				if (C[j] < C[i]) {
					if (D[j] > max) {
						max = D[j];
						D[i] = D[j] + 1;
					}
				}
			}
		}
		E[0] = 1;
		System.out.println(Arrays.toString(B));
		System.out.println(Arrays.toString(D));
		for (int i = 1; i < n; i++) {
			E[i] = Arrays.stream(Arrays.copyOfRange(B, 1, i + 1)).max().getAsInt()
					+ Arrays.stream(Arrays.copyOfRange(D, 1, n + 1 - i)).max().getAsInt();
			if((Arrays.stream(Arrays.copyOfRange(A, 1, i + 1)).max().getAsInt() == Arrays.stream(Arrays.copyOfRange(A, i+1, n + 1)).max().getAsInt())
					&& (Arrays.stream(Arrays.copyOfRange(B, 1, i + 1)).max().getAsInt()!=1) && (Arrays.stream(Arrays.copyOfRange(D, 1, n + 1 - i)).max().getAsInt()!=1))
				E[i]--;
		}
		System.out.println(Arrays.stream(E).max().getAsInt());
	}
}

nahwasa 4년 전 1

일단 기본 TC가 6으로 출력됩니다.

10
1 5 2 1 4 3 4 5 2 1

요거요..

뭔가 잘못올리신듯?

aka2344 4년 전 0

아 죄송합니다 코드를 잘못올렸네요 다시 올렸습니다

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

문제

문제

출처

ICPC

11054번 반례 있나요? 게시판에 있는 반례 해봤는데 다 제대로 됩니다

aka2344 4년 전 0

nahwasa 4년 전 1

aka2344 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말