글 읽기 - 붕어빵 판매하기 소스 수정후 틀리는데 반례를 모르겠습니다.

shoeskwang 5년 전 0

안녕하세요..

붕어빵 판매문제 때문에

1번 코드로 작성한 후 좀 더 좋은 성능을 내고자 2번 코드내용으로 변경을 하였는데요

해당 부분을 전체를 다시 확인할 필요없이 i , i-1 , i-2 까지만 비교해도 값이 구해지는데

왜 틀렸는지 이해가 잘 안갑니다.

조언 부탁드립니다...

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
	
	public static int max(int a,int b){
		return a>b?a:b;
	}

	public static void main(String[] args) throws Exception{
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
		st.nextToken();
		int n = (int)st.nval;
		
		int[] dp =  new int[n+1];
		for(int i=1;i<=n;i++){
			st.nextToken();
			dp[i]=(int)st.nval;
		}
        
----------------------------------------------------------------------------------
    /* 1번 코드 */
		for(int i=1;i<=n;i++){
			for(int j=1;j<i;j++){
				dp[i] = max(dp[i],dp[i-j]+dp[j]);				
			}
		}
------------------------------------------------------------------------------------
    /* 2번 코드 */
    	if(n>1){
			dp[2]= max(dp[2],dp[1]*2);
		}
		for(int i=3;i<=n;i++){
			for(int j=1;j<3;j++){
				dp[i] = max(dp[i],dp[i-j]+dp[j]);				
			}
		}
------------------------------------------------------------------------------------        
		System.out.println(dp[n]);
	}

}

jh05013 5년 전 0

정말로 옳은 풀이임을 증명할 수 있나요? 단순히 예제만 잘 돌아가는 것은 아닐까요?

jh05013 5년 전 0

20
1 1 1 1 1 1 1 1 1 100 1 1 1 1 1 1 1 1 1 1

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

문제

문제

출처

ICPC

붕어빵 판매하기 소스 수정후 틀리는데 반례를 모르겠습니다.

shoeskwang 5년 전 0

jh05013 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말