개발자 톡
연습문제 톡
효도 음식
자바 시간복잡도 문제
- 등록일
- 2024-02-01 20:55:50
- 조회수
- 623
- 작성자
- ddings7303
import java.io.*; import java.util.*; public class Main { static final int MIN = -1000; static int n; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer stk = new StringTokenizer(br.readLine()); n = Integer.parseInt(stk.nextToken()); arr = new int[n]; stk = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++){ arr[i] = Integer.parseInt(stk.nextToken()); } int[] sum = new int[n]; sum[0] = arr[0]; for(int i = 1; i < n; i++){ sum[i] = sum[i - 1] + arr[i]; } // 0 => 구간 하나 구한경우 // 1 => 구간 두개 구한경우 int[][] dp = new int[n][2]; for(int i = 0; i < n; i++){ dp[i][0] = arr[i]; dp[i][1] = MIN; } for(int i = 1; i < n; i++){ // 구간을 하나만 구한 경우 => 이전까지의 최대 또는 현재까지의 누적합 또는 arr[i] int prevOrSum = Math.max(dp[i-1][0], sum[i]); dp[i][0] = Math.max(dp[i][0], prevOrSum); for(int j = 0; j < i; j++){ dp[i][0] = Math.max(dp[i][0], sum[i] - sum[j]); } // 구간을 두개 둔 경우 => 어느 위치를 기준으로 구간을 나눴는지가 중요함 // 나눌 수 있는 위치는 1번부터 현재위치 - 1 for(int j = 1; j < i; j++){ // 현재 dp값과 왼쪽 최대 vs 오른쪽 포함한 새로운 구간합 비교 int leftOrRight = Math.max(dp[i - 1][1], dp[j-1][0] + (sum[i] - sum[j])); dp[i][1] = Math.max(dp[i][1], leftOrRight); } } System.out.println(dp[n - 1][1]); } }
나름 DP를 이용해서 구현했는데 시간초과가 나더군요..
혹시 다른 아이디어 힌트 가능할까요 ㅠ
#효도_음식