문제링크 : https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
이 문제를 보고 '그냥 모든 경우의 수를 다 구하면 안 되나?'란 생각이 들었다. 이 때의 시간 복잡도는 O(n^2)인데 n의 최댓값이 100,000이라 이 정도면 가능하지 싶었다. 코드는 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
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));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] seq = new int[n];
int[] sums = new int[n];
int max = Integer.MIN_VALUE;
int sum = 0;
for(int i = 0; i < n; i++) {
seq[i] = Integer.parseInt(st.nextToken());
sum += seq[i];
sums[i] = sum;
if(max < sums[i]) {
max = sums[i];
}
}
for(int i = 1; i < n; i++) {
for(int j = 0; j < i; j++) {
int tmp = sums[i] - sums[j];
if(max < tmp) {
max = tmp;
}
}
}
System.out.println(max);
}
}
|
맞긴 맞았는데 상위권 풀이와 비교해보니 시간 차이가 너무 많이났다-_- 이거이거 잘못 풀었구나...ㅠㅠ
제대로 푼 방법에 대한 설명을 하겠다. 0부터 n - 1까지 i를 증가시키면서 그 시점에서의 최댓값을 구한다. 그 시점에서의 최댓값이란, i = a라고할 때, 0부터 a까지의 수열 중에서 a가 선택되었을 때의 가장 큰 연속합을 의미한다. 아래의 수열을 예를 들어 설명해보겠다.
10 -4 3 1 5 6 -35 12 21 -1
i=0일 때 -> 10
i=1일 때 -> i=0일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 6
i=2일 때 -> i=1일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 9
i=3일 때 -> i=2일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 10
i=4일 때 -> i=3일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 15
i=5일 때 -> i=4일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 21
i=6일 때 -> i=5일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> -14
i=7일 때 -> i=6일때의 최댓값이 음수이므로 더하지 않는 것이 최대값 -> 12
i=8일 때 -> i=7일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 33
i=9일 때 -> i=8일때의 최댓값이 양수이므로 그 값을 더한 값이 최대값 -> 32
따라서 최댓값이 33임을 알 수 있다. 이 때의 시간 복잡도는 O(n)이다. 코드는 아래와 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
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));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] seq = new int[n];
seq[0] = Integer.parseInt(st.nextToken());
int maxCandidate = seq[0];
int max = maxCandidate;
for(int i = 1; i < n; i++) {
seq[i] = Integer.parseInt(st.nextToken());
if(maxCandidate > 0) {
maxCandidate = seq[i] + maxCandidate;
} else {
maxCandidate = seq[i];
}
if(max < maxCandidate) {
max = maxCandidate;
}
}
System.out.println(max);
}
}
|
'알고리즘' 카테고리의 다른 글
| 백준(BOJ) 1451 : 직사각형으로 나누기 (JAVA) (0) | 2020.02.10 |
|---|---|
| 백준(BOJ) 7453 : 합이 0인 네 정수 (JAVA) (0) | 2020.02.10 |
| 백준(BOJ) 11662 : 민호와 강호 (JAVA) (0) | 2020.02.07 |
| 백준(BOJ) 10816 : 숫자 카드 2 (JAVA) (2) | 2020.02.04 |
| 백준(BOJ) 2004 : 조합 0의 개수 (JAVA) (0) | 2020.02.04 |
