DP- 1912(연속합)

1912번: 연속합 (acmicpc.net)

1912번: 연속합

 

생각보다 간단했던 문제입니다. 하지만 메모리초과 부분에서 아쉬움이 있었습니다. 

n개의 정수로 이루어진 수열과 똑같은 크기의 수열을 하나 만들어서 연속해서 계속 더해줍니다. 그대신 연속해서 더한 수와 더하지 않고 그 자리에 있는 수만 더할 경우 두가지의 경우중 큰 경우를 새로 만들어준 배열에 저장하고 그 후, 그 배열중 최대값을 출력합니다.

 

package com.company;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());
        int number[] = new int[t];
        int sum[] = new int[t];
        int result = Integer.MIN_VALUE;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < t; i++) {
            number[i] = Integer.parseInt(st.nextToken());
            sum[i] = Integer.MIN_VALUE;
        }

        for (int i = 0; i < t; i++) {
            if (i == 0) {
                sum[i] = number[i];
            } else {
                sum[i] = Math.max(sum[i - 1] + number[i], number[i]);
            }
            if(result < sum[i]){result = sum[i];}

        }


        System.out.println(result);
    }
}

 

 

 

부족했던 점

처음에 제출한 답안은 메모리초과가 발생하였습니다. 조금 더 효율적인 코드를 작성하도록 해야합니다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int t = Integer.parseInt(br.readLine());
        int number [] = new int[t];
        int sum[][] = new int[t][t];
        int max = Integer.MIN_VALUE;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<t; i++){
            number[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i<t; i++){
            for(int j=i; j<t; j++){
                if(j == 0){ sum[i][j] = number[i]; }
                else{
                    sum[i][j] = sum[i][j-1]+number[j];
                }
                if(max < sum[i][j]){max = sum[i][j];}
            }
        }
        System.out.println(max);
    }
}