알고리즘/백준 풀이(동적 프로그래밍)
백준 2156번 - 포도주 시식
공부 기록장
2024. 1. 8. 18:28
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
이 문제는 계단 오르기 방식과 비슷한 형태의 문제이다.
백준 2579번 - 계단 오르기
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는
3946.tistory.com
먼저 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]);
}
}