글 읽기 - 왜 틀렸을까요...ㅠㅠㅠㅠ

rla7538 7년 전 0

제가 생각하는 테스트 예제를 돌려봣을때도 맞게 나오는데

어디가 틀렸는지 모르겠습니다... ㅠㅠ

import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;

/* 참고하시고 모르시는거 있으시면 댓글로 부탁드립니다~ */

class Main {
	static int n;
	static int input[];
	static int dp[][];
	static int count = 0;
	static int mem[];

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

		n = scan.nextInt();
		input = new int[n];
		dp = new int[n + 1][n + 1];
		for (int i = 0; i < n; i++) {
			input[i] = scan.nextInt();
		}
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				dp[i][j] = input[i] - input[j];
			}
		}
		/* Solution */

		match(0);
		System.out.println(count+1);

	}

	public static void match(int a) {
		int p,q;
		p = search_1(dp[a]);
		q = search_2(dp[a]);
		if (p != 0) {
			count++;
			match(p);
		}else if(q != 0){
			count++;
			match(q);
		}

	}

	public static int search_1(int arr[]) {
		int k = -9999;
		int t = 0;
		;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] < 0 && arr[i] > k) {
				k = arr[i];
				t = i;
			}
		}
		return t;
	}

	public static int search_2(int arr[]) {
		int k = 9999;
		int t = 0;
		;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > 0 && arr[i] < k) {
				k = arr[i];
				t = i;
			}
		}
		return t;
	}

	public static void println(int arr[][]) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(arr[i][j] + "\t");
			}
			System.out.println();
		}

	}

	public static void println(int arr[]) {
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

}

artage7 6년 전 0

dp로 푸셨으면 점화식이든 뭐든 적어주시지... 전 자바 몰라서 보기 힘드네요.

해결하셨는지는 모르겠으나

가장 긴 부분 수열 시리즈를 푸셨다면...

1 5 2 1 4 3 4 5 2 1 가 있을 때 ( 굵은 숫자가 정답의 기준이 되는 수 )

10번 인덱스 부터 1번 인덱스 까지 감소하는 가장 긴 수열을 dp로 구합니다.

그러면 10번 -> 1번 방향으로 가장 긴 감소 수열이 구해지니깐

예제 정답의 기준인 8번 인덱스 부터 1번 인덱스 까지의 가장 긴 감소하는 수열의 길이(dp[8][0])이 구해질 것이고.

똑같은 방법으로

1번 인덱스 부터 10번 인덱스 까지 감소하는 가장 긴 수열을 dp로 구합니다.

그러면 1번 -> 10번 방향으로 가장 긴 감소 수열이 구해지니깐

에제 정답의 기준인 8번 인덱스 부터 10번 인덱스 까지의 가장 긴 감소하는 수열의 길이(dp[8][1])을 구할 수 있습니다.

두개를 더하고 8번 위치는 두번 더해지니깐 -1 하면 답.

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