Q. 5642. 합(D3)

Q. 5642. 합(D3)

 

0. 문제

 

D3 난이도의 문제이고, DP를 이용한 문제이다.

수열이 주어지고 연속해서 원소를 골라 합을 구할 때, 그 합의 최대가 몇인지 구하는 프로그램을 작성하는 문제이다

---

1. 풀이

 

두 가지의 풀이 방법이 생각났다.

첫번재는 DP를 이용한 풀이이고, 두 번째는 투 포인터를 이용한 풀이이다.

 

1-1 DP를 이용한 풀이

DP인 경우 보통 정답이 dp[N - 1]인데, 이 문제의 경우는 그렇게는 정답을 구할 수 없어서 조금 시간이 걸렸다.

 

아래와 같은 방식으로 풀었다.

1) 반복문을 N-1까지 돌면서, 현재 인덱스의 숫자와 이전에 저장된dp + 현재 인덱스의 숫자를 비교해 큰 값을 dp에 저장한다.

2) dp 배열에 저장된 값 중 최대값을 저장한다.

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Solution {
 
    static BufferedReader br;
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
     
 
    static int N;
    static int[] inputArr;
    static int[] dp;
     
    static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        inputArr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) inputArr[i] = Integer.parseInt(st.nextToken());
        dp = new int[N];
    }
     
    static void pro(int tc) throws Exception{
         
        dp[0] = inputArr[0];
        int max = inputArr[0];;
        for (int i = 1; i < N; i++) {
            dp[i] = Math.max(dp[i - 1] + inputArr[i], inputArr[i]);
            max = Math.max(dp[i],  max);
        }
         
        sb.append(String.format("#%d %d\n", tc, max));
    }
     
    public static void main(String[] args) throws Exception{
         
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));
         
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
            input();
            pro(tc);
        }
        System.out.println(sb);
         
    }
 
}

---

1-2 투 포인터를 이용한 풀이

 

투 포인터는 간단히 요약하면 두 개의 변수를 이용해 필요한 부분만 필요한 만큼 탐색하는 방식이다.

핵심은 두 개의 변수이고, 보통 두 변수가 모두 탐색하는데 O(2N)의 시간복잡도를 가진다.

 

아래와 같은 방식으로 풀었다.

1) L과 R을 선언하고, N까지 반복하며 각 원소들의 합을 저장한다.

2) 이 때 원소들의 합이 0보다 작을 경우 sum을 0으로 초기화하며, 원소들의 합을 저장할 때 마다 최대값을 저장한다.

3) R이 끝까지 도달하면 종료한다.

 

코드는 아래와 같다.

import java.io.*;
import java.util.StringTokenizer;

class Solution {


    static StringBuilder sb = new StringBuilder();
    static BufferedReader br;
    static StringTokenizer st;


    static int N;
    static int[] inputArr;

    static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        inputArr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) inputArr[i] = Integer.parseInt(st.nextToken());
    }

    static void pro(int tc) throws Exception{

        int R = 0, L = 0;
        int sum = 0;
        int max = inputArr[0];

        while(R < N) {
            sum += inputArr[R];
            max = Math.max(max, sum);

            if(sum < 0) {
                L = ++R;
                sum = 0;
            }else R++;
        }
        sb.append(String.format("#%d %d\n", tc, max));
    }

    public static void main(String[] args) throws Exception{

        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("res/input.txt")));

        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
            input();
            pro(tc);
        }
        System.out.println(sb);

    }

}

---

2. 시간복잡도 계산

 

0) N의 최대값은 100000이다.

1) 입력값 저장 - O(N)

2) dp, 투 포인터 - O(N)

따라서 두 풀이 모두 시간복잡도는 O(N)이고, 시간제한은 2초이므로 1초 이내에 풀 수 있다.