더럽게 오래걸렸네 진짜루
이 문제는 연속합1 의 응용버전으로, 수열에서 수 하나를 지울 수도 있다는 조건이 추가돼있다.
전체적으로는 두 가지 경우로 나누어서 최댓값을 찾아야한다.
- 나까지 아무것도 삭제하지 않을 때의 최댓값 저장
- 나 포함 내 이전에 특정 수 삭제 할 때의 최댓값 저장
첫 번째 경우는 부분합1 문제와 동일하다. 헷갈리는 부분은 그 다음인데, 두 번째 경우가 다시 두 가지 경우로 나뉜다. for문 안에서
2-1. 이전 수가 삭제되지 않은 경우, 나를 삭제
2-2. 이전 수들 중에서 삭제된 게 있으면 삭제 불가 (나를 더한다)
하여튼 이런 생각은 어떻게 하는건지 모르겠다. 나도 알고리즘 로봇이 되고싶다.
위의 풀이법을 보고 내가 작성한 코드인데 틀린 코드다. 일단은 보자.
// 틀린 코드 틀린 코드 틀린 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int[] seq = new int[N+1];
StringTokenizer st = new StringTokenizer(in.readLine());
for(int i = 1; i <= N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
int[][] dp = new int[N+1][2];
int max = seq[1];
for(int i = 1; i <= N; i++) { // seq(1, i) 부분문제 풀기
// 아무것도 삭제하지 않을 경우의 최댓값
dp[i][0] = Math.max(dp[i-1][0]+seq[i], seq[i]);
// 하나 삭제할 때의 최댓값 !! 여기 틀림
dp[i][1] = Math.max(dp[i-1][1]+seq[i], dp[i-1][0]);
// 최종답 ✨
max = Math.max(max, Math.max(dp[i][0],dp[i][1]));
}
System.out.println(max);
}
}잘 짠 거 같지? 일단 첨엔 그랬지...😭
근데 이 예제를 생각해보자. 이건 사실 부분합1의 예제인데, 예외를 생각하기 좋은 테스트케이스다.
이 수열이 들어오면 i=1 일 때 dp[1][1]에 seq[1]이 아니라 dp[i-1][0] = 0 이 대입된다.
한마디로 원래 첫 번째 원소가 뭐든간에 dp[1][0] = dp[1][1] = seq[1] 이어야 하는 건디 첫 번째 원소가 음수면 dp[1][1]에 0이 들어가서 틀렸다.
그래서 코드를 이렇게 고치면 된다.
int[][] dp = new int[N+1][2];
// 첫 번째는 초기화를 해줘야 함
dp[1][0] = dp[1][1] = seq[1];
int max = seq[1];
// 두 번째부터 반복문 돌리기!_!
for(int i = 2; i <= N; i++) {
dp[i][0] = Math.max(dp[i-1][0]+seq[i], seq[i]);
dp[i][1] = Math.max(dp[i-1][1]+seq[i], dp[i-1][0]);
max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
}
System.out.println(max);근데 이렇게 초기화할거면 배열크기 +1 안하고 크기N으로 맞추는게 나을 거같다.
이런게 정말 헷갈린다 😥 상황에 맞게 바꿔가며 해야하는 건지 아니면 무조건 초깃값을 정해주는게 좋은건지 모르겠다. 어떤게 좋은건지 알려줬으면~
