글 읽기 - 문제의 조건이 이해가 되지 않습니다.

henry1993 4년 전 1

dp[n] = dp[i-2] + arr[i]                // 마지막계단과 전전계단까지의 최댓값
dp[n] = dp[i-3] + arr[i-1] + arr[i]     // 마지막계단과 전계단, 전전전계단까지의 최댓값

대부분 문제 풀이에 대한 점화식이 위처럼 되어 있는데

마지막 계단을 밟지 않으면 안된다는 조건을 왜 점화식부터 적용하는지 이해가 가지 않습니다.

전체 계단이 주어진 상황에서 마지막 계단을 밟지않는 경우만 예외조건으로 제외하면 되는거 아닌가요?

저는 전체 주어진 계단에서 마지막 계단만 밟으면 된다고 생각하여 입력 값을 거꾸로 넣고 풀었습니다.(위에서 부터 내려오는 것처럼)

혹시 반례나 제가 잘못생각하고 있는 부분이 있을까요?

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    int[] numbers = new int[300];
    for (int i = 0; i < n; i++) {
      numbers[(n-1)-i] = sc.nextInt();
    }

    int[] dp = new int[300];

    dp[0] = numbers[0];
    dp[1] = numbers[0] + numbers[1];
    dp[2] = Math.max(dp[0] + numbers[2], dp[1]); 

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

    System.out.println(dp[n-1]);

  }
}

shg9411 4년 전 0

점화식을 이해를 잘못하신 것 같습니다.

세 계단을 연속으로 밟지 않기 위해..

henry1993 4년 전 0

셰 계단을 연속으로 밟지 않는 경우가

o o x

o x o

x o o

3가지 경우 아닌가요? ㅠㅠ

예시로 든 점화식은 o x o 와 x o o 는 표현되어 있는데 o o x는 왜 표현이되어 있지 않은건가요?

shg9411 4년 전 0

oox?

1234번 인덱스라고 생각하시면

4번 인덱스에서 첫번째 점화식에 해당됩니다.

dp[n] = dp[i-2] + arr[i]//위에 작성하신 점화식
dp[4] = dp[4-2] + arr[4]//현재 ? 위치

henry1993 4년 전 0

혹시 반례를 하나 들어주실 수 있나요? ㅠㅠ

아직 잘 이해가 되지 않습니다. 예를보면서 풀면 이해가 더 잘될거같은데..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제의 조건이 이해가 되지 않습니다.

henry1993 4년 전 1

shg9411 4년 전 0

henry1993 4년 전 0

shg9411 4년 전 0

henry1993 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말