백준 13398번
-
[Dev-Ping9] 백준 13398번 : 연속합 2 (Java)코딩테스트/백준 2021. 11. 8. 21:03
# Description # 어떤 접근 방법이 좋을까? 1. 문제의 답은 최적의 해를 구하는 것 2. 이전의 해를 이용하여, 지금의 해를 구할 수 있는가? (부분 구조가 성립하는가? => Yes) => 1번과 2번 문항을 통해 DP를 적용 시킬 수 있다는 근거를 가지게 되었다. 3. 단순무식하게 풀었을 때 연산량이 많은가? f(a) 를 a 부터 시작한 [연속합2] 의 최대라 정의 했을때, => 1~N , 2~N , 3~N, .... , N~N => O(N^2) 4. 공간의 제약이 많은가, 시간의 제약이 많은가 => Description을 보면, 확실히 시간의 제약이 많다. (시간제한 및 n의 최대값) => 보통 1초에 1억번 연산가능 (N^2 이면, N=100_000일때, 1천억번 연산해야함 => 1천초..