글 읽기 - 시간초과 문제

yoonys427 6년 전 1

채점이 100%까지 가는데 시간초과에 걸리네요...

Bottum-up 방식이 아니라 Top-Down이라 그런건지... 잘 모르겠네요 ㅠㅠ

어디서 시간을 줄일 수 있는지 잘 모르겠어요 도와주세요...

import java.util.*;
import java.io.*;

public class Main {
	
	public static int d[][];
	public static int point[][];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		for (int i=0; i<n; i++) {
			
			int num = Integer.parseInt(br.readLine());
			point = new int[num+1][2];
			
			String[] point_line1 = br.readLine().split(" ");
			String[] point_line2 = br.readLine().split(" ");
			
			for (int j=0; j<num; j++) {
				point[j+1][0] = Integer.parseInt(point_line1[j]);
				point[j+1][1] = Integer.parseInt(point_line2[j]);
			}
			
			d = new int[num+1][3];
			
			int result = 0;
			result = Math.max(Math.max(solve(num, 0), solve(num, 1)), solve(num, 2));
			
			System.out.println(result);
			
		}
	}
	
	public static int solve(int num, int stat) {
		
		if (num == 1 && stat == 0)
			return point[1][0];	
		
		if (num == 1 && stat == 1)
			return point[1][1];
		
		if (num == 1 && stat == 2)
			return 0;
		
		if (d[num][stat] > 0)
			return d[num][stat];
		
		int temp = 0;
		
		if (stat == 0) {
			temp = Math.max(solve(num-1, 1), solve(num-1, 2)) + point[num][stat];
		}
		if (stat == 1) {
			temp = Math.max(solve(num-1, 0), solve(num-1, 2)) + point[num][stat];
		}
		if (stat == 2) {
			temp = Math.max(solve(num-1, 1), solve(num-1, 2));
			temp = Math.max(temp, solve(num-1, 0));
		}
		
		d[num][stat] = temp;
		return temp;
	}
}

djm03178 6년 전 2

최근에 데이터가 추가되었는데, 딱 이런 코드를 저격한 데이터입니다.

47,48번째 줄이 문제입니다. 왜 이게 시간 초과를 유발할지 생각해보세요. 힌트는 점수의 범위입니다.

yoonys427 6년 전 1

@djm03178

점수가 0일때가 문제였군요.

d 배열의 초기값을 -1로 변경하고 하니 해결됐습니다.

감사합니다!

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

문제

문제

출처

ICPC

시간초과 문제

yoonys427 6년 전 1

djm03178 6년 전 2

yoonys427 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말