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초 이내에 풀 수 있다.