[백준] 계단 오르기 vs 포도주 시식 - 자바

✔️ 계단 오르기

규칙

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

 

 

우선 계단의 점수와 현재 도착한 방법 중 최대값을 저장할 변수를 선언한다.

int[] dp = new int[N+1];
int[] stair = new int[N+1];

 

첫 번째 계단은 첫 번째 계단에 도착했을 때 최대값을 가짐   dp[1] = stair[1]

두 번째 계단은 첫번째 계단에서 올랐을 때 최대값을 가짐   dp[2] = stair[1] + stair[2];

세 번째 계단은 첫 번째, 두 번째 계단 중 더 큰 값에서 올랐을 때 최대값을 가짐  dp[3] =  Math.max(stair[1], stair[2]) + stair[3];

 

if (N > 1), if (N > 2) 조건은 범위가 자연수 이므로 붙여주었음

dp[1] = stair[1];
if (N > 1) dp[2] = stair[1] + stair[2];
if (N > 2) dp[3] = Math.max(stair[1], stair[2]) + stair[3];

 

네 번째 계단 부터는 경우의 수를 생각할 필요가 있다!

• 2를 거쳐 4로 올라오는 경우

2에서 2칸을 올라오는 경우이므로 이전에 올라온 방법이 관계가 없다. 한 칸도, 두 칸도 모두 올라올 수 있어 이미 최대 값이 저장되어 있다. 따라서 2에 도착한 최대값에서 4의 계단의 점수를 더해준 값을 구할 수 있다.

 

• 3을 거쳐 4로 올라오는 경우

3에서 1칸을 올라오는 경우이므로 이전에 1칸만 올라온 경우는 없어야한다. 무조건 두 칸 올라온 후 한 칸을 올라와야한다. 따라서 1에 도착한 최대값에서 3과 4의 계단의 점수를 더해준 값을 구할 수 있다.

3에 도착한 최대값에서 4의 계단의 점수를 더해주면 2에서 한 칸 올라온 경우도 포함하므로 1의 최대값에서 3, 4 계단값을 더해야한다.

 

따라서 이 두 가지 방법 중에 큰 값을 저장할 수 있다.

 

마지막 도착 계단은 반드시 밟아야 하므로 마지막까지 계산한 후 마지막의 값을 반환한다.

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N+1];
        int[] stair = new int[N+1];

        for (int i = 1; i <= N; i++) {
            stair[i] = Integer.parseInt(br.readLine());
        }

        dp[1] = stair[1];
        if (N > 1) dp[2] = stair[1] + stair[2];
        if (N > 2) dp[3] = Math.max(stair[1], stair[2]) + stair[3];

        for (int i = 4; i <= N; i++) {
            dp[i] = Math.max(stair[i-1] + dp[i-3], dp[i-2]) + stair[i];
        }

        System.out.println(dp[N]);
    }
}

 

 

✔️ 포도주 시식

규칙

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

계단 문제와 비교했을 때 바뀐 부분

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
   → 상관 없음 세 번 건너 뛰어도 괜찮다.
   
   
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
   → '연속으로 놓여 있는 3잔을 모두 마실 수는 없다.' 와 일치하는 규칙
   
   
3. 마지막 도착 계단은 반드시 밟아야 한다.
   → 도착지점은 상관 없음

 

처음에는 계단 문제와 비슷하게 풀어보았다. 그치만..! 실패하였음

계단은 1, 2번만 건너뛸 수 있지만 포도주는 3번 이상 건너 뛰어도 괜찮다는 조건을 유의할 필요가 있었다..!

 

 

예시

 

10 + 10 + 10 + 10 = 40이 최대로 마실 수 있는 포도주량이지만

 

 

• 계단 문제처럼 풀었을 때

계단 문제처럼 풀면 한 번에 한 계단씩 또는 두 계단씩의 조건 때문에

앞의 10, 10을 택한 후에 두 번째 1을 택할 수밖에 없다.

 

 

하지만 두 번째 1이 선택되면 연속해서 10을 선택할 수 없다.

따라서

10 + 10 + 1 + 10 + 1 = 32가 최대로 마실 수 있는 포도주량이 된다. 이것은 최대가 아니다!

 

 

 

 

풀이

첫 번째 계단은 해당 계단의 점수로 밖에 도착할 수 없음

두 번째 계단은 첫번째 계단에서 도착했을 때 최대값

 

if (N > 1) 조건은 N의 범위가 (1 ≤ N ≤ 10,000) 이므로 N = 1일 때를 대비하여 붙여줌

int[] dp = new int[N+1];
dp[1] = num[1];
if (N > 1) dp[2] = num[1] + num[2];

 

 

• 2를 마시고 4를 마시는 경우
• 3을 마시고 4를 마시는 경우

는 계단 문제와 동일하게 이 두 가지 방법 중에 큰 값을 구할 수 있다.

 

하지만 4를 마시지 않는 방법도 생각해야하므로 3까지 계산한 최대값과 최종적으로 비교해야한다.

for (int i = 3; i <= N; i++) {
    dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + num[i-1], dp[i-2]) + num[i]);
}

 

 

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] num = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            num[i] = Integer.parseInt(br.readLine());
        }


        int[] dp = new int[N+1];
        dp[1] = num[1];
        if (N > 1) dp[2] = num[1] + num[2];
        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + num[i-1], dp[i-2]) + num[i]);
        }

        System.out.println(dp[N]);
    }
}