백준
DP #1912: 연속합 [JAVA]
chaechaepower
2023. 6. 26. 23:15
https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
한 시간 동안 헛짓 함
이것도 다 경험이지~....
코드
top down - 재귀 (내 풀이)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] seq;
static Integer[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
seq = new int[N];
dp = new Integer[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
dp[0] = seq[0];
int max = dp[0];
for (int i = 1; i < N; i++) {
int comp = recur(i);
if (comp > max) {
max = comp;
}
}
System.out.println(max);
}
static int recur(int n) {
if (dp[n] == null) {
dp[n] = Math.max(dp[n], seq[n] + recur(n - 1));
}
return dp[n];
}
}
top down - 재귀 (std-lab님)
다 똑같은데 max 구하는 부분 참고 !
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] seq;
static Integer[] dp;
static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
seq = new int[N];
dp = new Integer[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
dp[0] = seq[0];
max = seq[0];
recur(N - 1);
System.out.println(max);
}
static int recur(int n) {
if (dp[n] == null) {
dp[n] = Math.max(seq[n], seq[n] + recur(n - 1));
max = Math.max(max, dp[n]);
}
return dp[n];
}
}