글 읽기 - [자바] 시간초과 나오네요. 잘못된 방법인가요?

chljy33 6년 전 0

if 문으로 조건을 걸었더니 시간 초과 나와서 switch 문으로 변경해도 여전히 시간초과가 나오더군요.

정답은 맞게 나오고 있는데, 시간 초과 해결하려면 배열을 써야 하나요?

왜 이 방법은 느린 방법인지 궁금합니다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Main m = new Main();
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		m.stairs = new int[n];
		
		for(int i=0; i<n; i++){
			m.stairs[i] = sc.nextInt();
		}
		
		// 1: 10, 2: 01, 3:11, 4: 1, 5: 0
		
		int res = m.goUpStair(0, -1);
		
		System.out.println(res);
	}
	
	int stairs[];
	
	int goUpStair(int pos, int code){
		if(pos == 0){
			return Math.max(goUpStair(pos+1, 4)+this.stairs[pos],goUpStair(pos+1, 5));
		}
		if(pos == 1 && code == 4){
			return Math.max(goUpStair(pos+1, 3)+this.stairs[pos],goUpStair(pos+1, 1));
		} else if(pos == 1 && code == 5){
			return goUpStair(pos+1, 2)+this.stairs[pos];
		}
		if(pos > 1 && pos < this.stairs.length - 2){
			switch (code) {
			case 1:
				return goUpStair(pos+1, 2) + this.stairs[pos];
			case 2:
				return Math.max(goUpStair(pos+1, 3) + this.stairs[pos], goUpStair(pos+1, 1));
			case 3:
				return goUpStair(pos+1, 1);
			default:
				break;
			}
		}
		if(pos == this.stairs.length - 2){
			switch (code) {
			case 1:
				return goUpStair(pos+1, 2) + this.stairs[pos];
			case 2:
				return goUpStair(pos+1, 1);
			case 3:
				return goUpStair(pos+1, 1);
			default:
				break;
			}
		}
		if(pos == this.stairs.length - 1){
			return this.stairs[pos];
		} 
		return 0;
	}
}

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

문제

문제

출처

ICPC

[자바] 시간초과 나오네요. 잘못된 방법인가요?

chljy33 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말