문제 링크
문제
티어: 골드 1
알고리즘: dp
정보올림피아드 경시장으로 가는 길에 자연수 값이 적힌 타일이 한 줄로 깔려있다. 철수는 타일에 적힌 자연수 값은 모두 다르고 시작에서부터 증가하는 순서로 깔려있음을 확인하였다.
철수는 임의의 한 타일에서 시작하여 몇 개의 타일을 밟아서 경시장으로 가려고 한다. 단, 타일들에 적힌 숫자가 일정한 자연수만큼 증가하도록 밟으려고 한다.
그러나 철수는 시작하는 위치와 증가하는 값에 따라 연속적으로 밟을 수 있는 타일의 개수가 달라지는 것을 알 수 있었다.
철수는 경시장으로 가면서 위와 같은 방법으로 연속적으로 밟을 수 있는 타일에 적힌 수들의 합 중에서 최댓값은 얼마나 될까 계산하여 보기로 하였다. 연속적으로 밟을 수 있는 타일의 개수는 적어도 3개 이상이어야 한다.
예를 들어 타일에 적힌 자연수들의 순서가 다음과 같이 주어졌다고 하자.
1, 2, 6, 7, 11, 12, 13, 15, 17, 20, 23
이 경우 철수가 연속적으로 밟을 수 있는 타일들의 모든 가능한 순서를 열거하면 다음의 표와 같다. 표에 열거한 것 외에 타일을 연속적으로 3개 이상 밟을 수 있는 경우는 없다.
따라서 이 예에 대해 철수가 경시장으로 가면서 시작하는 타일을 포함하여 연속적으로 밟을 수 있는 타일에 적힌 수들의 합 중에서 최댓값은 60이다.
타일에 적힌 수들이 증가하는 순서로 주어질 때, 철수가 연속적으로 밟을 수 있는 타일이 3개 이상 있는 경우, 그렇게 연속적으로 밟을 수 있는 타일에 적힌 수들의 합 중에서 최댓값을 출력하는 프로그램을 작성하시오. 연속해서 타일을 3개 이상 밟을 수 있는 경우가 존재하지 않으면 0을 출력한다.
입력
첫째 줄에는 타일의 개수 N이 주어진다. N은 3 이상 3,000 이하이다. 둘째 줄에는 N개의 타일에 적힌 자연수들이 증가하는 순서로 빈칸을 사이에 두고 주어진다. 타일에 적힌 자연수들은 각각 1,000,000 이하이다.
출력
철수가 연속적으로 3개 이상 밟을 수 있는 타일이 존재하면, 그렇게 연속적으로 밟은 타일에 적힌 수들의 합 중에서 최댓값을 첫째 줄에 출력하시오. 연속해서 타일을 3개 이상 밟을 수 있는 경우가 존재하지 않으면 0을 출력한다.
풀이
철수가 연속적으로 3개 이상 밟을 수 있는 타일이 존재하면, 그렇게 연속적으로 밟은 타일에 적힌 수들의 합 중에서 최댓값을 첫째 줄에 출력해야 한다.
1부터 N까지 증가하는 관점에서 본다면
N이 3일 때
1 2 6
마지막이 6이면 가능한 모든 경우는
1 - 6, 2 - 6, 6이다.
N이 5일 때를 보면
1 2 6 7 11이고,
마지막이 11이면 가능한 모든 경우는
1 - 11, 2 - 11, 6 - 11, 7 - 11, 11이다.
여기서 6 - 11을 보면 차이가 5인데 만약 6과 그 보다 작은 수랑 일정한 값인 5로 연결되어 있다면, 단순히 6 - 11보다 1 - 6 - 11이 더 큰 값을 가진다.
그래서 이를 토대로 dp를 정의하면 각 인덱스마다 현재 인덱스가 마지막이라고 했을 때 그 보다 작은 값들 중 일정한 값으로 연결될 수 있는 모든 경우를 유지한다면, 다음 인덱스에서 모든 경우를 구할 때 이미 구해놓은 값을 활용할 수 있게 된다.
예를 들어 dp[3]의 일정한 값이 5인 값들의 합은 1 - 6으로 7이 되고, dp[5]와 6(3번 째)이 연결되었을 때의 최댓값을 구할 때 이를 활용하면 dp[3]의 7과 11을 더해서 dp[5]의 일정한 값이 5인 값들의 최댓값은 18임을 O(1)로 구할 수 있다.
그래서 시간 복잡도는 1 ~ 3000까지의 합이 된다. 왜냐하면 각 인덱스에서는 그 전 모든 인덱스를 한 번씩 방문하기 때문이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static long answer = 0;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[N + 1];
HashMap<Integer, Long>[] dp = new HashMap[N + 1];
for(int i=1; i<=N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
dp[i] = new HashMap<>();
}
for(int i=2; i<=N; i++) {
for(int j=i - 1; j>=1; j--) {
int diff = arr[i] - arr[j];
if(dp[j].get(diff) == null) {
dp[i].put(diff, (long) arr[j] + arr[i]);
} else {
long v = dp[j].get(diff) + arr[i];
dp[i].put(diff, v);
answer = Math.max(answer, v);
}
}
}
System.out.println(answer);
}
}