글 읽기 - 자바로 짠 9465번 스티커 문제인데 시간초과가자꾸뜹니다.

woo81479308 8년 전 0

안녕하세요~ 9465번 스티커문제를풀다 시간초과에 막혀서 질문드립니다.

DP로 나름 짜봤고 테스트케이스도 잘 돌아가구요..

기껏해야 반복문 N번 정도 도는게 끝일텐데 .. N이 최대값이 10만인데 왜 시간초과가뜨는지 잘 모르겠네요..

조언좀 부탁드리겠습니다~

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	
	public static void main( String [] arg ){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		int[] max = new int[1000000];
		int max_idx = 0;
		for(int testCase = 0; testCase<T; testCase++){
			
			
			int N = sc.nextInt();
			int[][] arr = new int[2][N];
			int[][] dp = new int[N+1][2]; //내가 위에꺼 먹었으면 0번에값이
			                              //아래꺼 먹었으면 1번에 값이
			
			
			for(int i=0; i<2; i++){
				for(int j=0; j<N; j++){
					arr[i][j] = sc.nextInt();
				}	
			}
			if(arr[0][0]>arr[1][0]){
				dp[1][0] = arr[0][0];
			}else{
				dp[1][1] = arr[1][0];
			}
			
			dp[2][0] = dp[1][1] + arr[0][1];
			dp[2][1] = dp[1][0] + arr[1][1];
			
			for(int i=3; i<N+1; i++){
				dp[i][0] = max(dp[i-1][1] + arr[0][i-1], 
						dp[i-2][0] + arr[0][i-1],	
						dp[i-2][1] + arr[0][i-1]);
				
				dp[i][1] = max(dp[i-1][0] + arr[1][i-1], 
						dp[i-2][1] + arr[1][i-1],
						dp[i-2][0] + arr[1][i-1]);
			}
			max[max_idx++]= dp[N][0] > dp[N][1] ? dp[N][0]:dp[N][1];
			
		}
		for(int i=0; i<max_idx; i++){
			System.out.println(max[i]);
		}
	}
	public static int max(int a, int b, int c){
		int[] arr = new int[3];
		arr[0] = a;
		arr[1] = b;
		arr[2] = c;
		Arrays.sort(arr);
		return arr[2];
	}
}

algoshipda 8년 전 1

이 문제가 입력데이터가 많아서 입출력에 많이 걸려요.

http://codeforces.com/blog/entry/6834 이게 도움이 될것 같아요.

woo81479308 8년 전 0

ㄴ 감사합니다!! 덕분에 또 새로운걸 알아가네요! 해결됬습니다^^

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

문제

문제

출처

ICPC

자바로 짠 9465번 스티커 문제인데 시간초과가자꾸뜹니다.

woo81479308 8년 전 0

algoshipda 8년 전 1

woo81479308 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말