https://www.acmicpc.net/problem/2156
이 문제는 계단 오르기 방식과 비슷한 형태의 문제이다.
먼저 N=5 까지의 경우의 수를 직접 계산해봤고 N=5 일 때를 가정하여 풀었다.
dp[5] 의 값 중 1+3+4 는 dp[i-1] 의 값을 포함하고 있고
dp[5] 의 값 중 2+3+5 와 1+3+5 는 dp[i-2] 의 값에 arr[i] 을 더한 값을 포함하고 있다.
그리고 나머지 1+2+4+5 는 dp[i-3] 값에 arr[i-1] + arr[i] 를 더한 값을 포함하고 있다.
따라서 i가 3 이상일 때 다음과 같은 식이 성립한다.
dp[i] = Math.max(dp[i-1],Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]));
코드(bottom-up 방식)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int arr[] = new int[N+1];
int dp[] = new int[N+1];
for(int i=1;i<N+1;i++){
arr[i] = sc.nextInt();
}
dp[0]=0;
dp[1] = arr[1];
if(N>1)
{
dp[2] = arr[1] + arr[2];
}
for(int i=3;i<=N;i++)
{
dp[i] = Math.max(dp[i-1],Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]));
}
System.out.println(dp[N]);
}
}
'알고리즘 > 백준 풀이(동적 프로그래밍)' 카테고리의 다른 글
백준 11053번 - 가장 긴 증가하는 부분 수열 (0) | 2024.01.10 |
---|---|
백준 2193번 - 이친수 (0) | 2024.01.09 |
백준 1912번 - 연속합 (1) | 2024.01.05 |
백준 1149번 - RGB거리 (1) | 2024.01.04 |
백준 1003번 - 피보나치 함수 (0) | 2024.01.02 |