글 읽기 - 시간초과!!!!

cedar0 8년 전 0

시간초과가 나오는데...

3중 for문으로 밖에 생각이 안나네요

알고리즘 좀 알려주세요^^

import java.util.Scanner;

public class T_1912 {
 
    public static void main(String[] args) { 
    	Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
    	int[] nn = new int[n];
    	for(int i=0;i<n;i++){
    		nn[i]=sc.nextInt();
    	}
    	int tot=0;
    	int max=nn[0];
    	for(int h=0;h<n;h++){
    		for(int k=h;k<n;k++){
        		for(int i=h;i<=k;i++){
        			tot+=nn[i];
            	}	
        		if(tot>max)max=tot;
        		tot=0;
        	}	
    	}
    	System.out.println(max);
    }
}

sgchoi5 8년 전 0

hint 에 보시면 dynamic programming 이라고 되어 있네요.

dynamic programming 은 memo 에 중복되는 계산값을 미리 저장해 두고 쓰는 방식으로 계산 회수를 줄여야 합니다.

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

문제

문제

출처

ICPC

시간초과!!!!

cedar0 8년 전 0

sgchoi5 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말