글 읽기 - 답은 맞았지만 왜 그런지 모르겠습니다.

hoguma33 6년 전 0

21 라인에서 dp배열에 초기화를 안해주고

dp[0] = progression[0];

dp[1] = progression[1];

이 두개만 써도 같은것 아닌가요? 제출하면 틀렸다고 나옵니다..

package backjoonPractice;

import java.io.*;

/* 가장 큰 증가 부분 수열  */

public class Highestprogression {

	public static void main(String[] args) throws NumberFormatException, IOException  {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		String [] Num = br.readLine().split(" ");
		int [] progression = new int[N];
		int [] dp = new int[N];
		int max = 0;
		
		for (int i = 0; i < Num.length; i++) {
			progression[i] = Integer.parseInt(Num[i]);
			dp[i] = progression[i];
		}
		max   = progression[0];
		
		for (int i = 1; i < N; i++) {
			for (int j = 0; j < i; j++) {
				
				if(progression[i] > progression[j] && dp[i] < dp[j] + progression[i])
				{
					dp[i] = dp[j] + progression[i];
				}
				System.out.println(dp[i]);

				if(dp[i] > max) max = dp[i];
			}
			System.out.println("i : " +i +" max : "+max);

		}
		System.out.println(max);
	}

}

seico75 6년 전 0

3 2 1 2 3 4 5

i번째 요소까지 고려하면 조건에 해당하는 j 를 찾아서 dp[i] 를 갱신하는데 j가 없이 i 하나만 쓰는 경우도 있기 때문에 이것을 고려해줘야하겠죠.

다르게 보면 i=4 일때 dp는 i=0, 1, 2, 3 까지 차 있을텐데, j = 0일때 if(progression[i] > progression[j] && dp[i] < dp[j] + progression[i]) 를 계산할 때

dp[i] = dp[4] 를 쓰죠. 아직 값을 넣지 않은...

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

문제

문제

출처

ICPC

답은 맞았지만 왜 그런지 모르겠습니다.

hoguma33 6년 전 0

seico75 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말