[백준 알고리즘](DP) 2579번 Java 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 1105

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

알고리즘 문제풀이(PS) 시작하기

 

백준 알고리즘 2579번

 

 

요즘 한동안 DP문제에 손을 못대고, 최근 파이썬을 공부하게 되면서 오랜만에 풀다보니 감이 많이 떨어졌다. 문제 접근까지는 비슷하게 갔는데, 마지막 계단을 반드시 밟는다는 조건을 못 풀고 있었다. 다른 분의 풀이를 참고해보니 역순으로 접근하면 되는 것... 이전에도 유사한 문제가 있었는데 내가 아예 까먹은 것 같다..ㅠㅠ

처음에는 시작하는 위치에서 증가하는 방향으로 행동을 Select, Not 2개로 정의한 뒤, 경우의 수를 쭉 나열해보고 Not select를 하는 순간부터 연속 select 조건이 사라지므로 SSN, SN, N으로 세 가지로 추려냈다. 그리고 조건 중 마지막 계단을 반드시 밟는 다는 조건에서 헤매다가 결국 다른 분의 풀이를 참고했다.
https://limkydev.tistory.com/121

 

<정답 풀이>

package dp;
 
import java.util.Scanner;
 
public class N2579 {
 
    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;i++) {
            arr[i] = sc.nextInt();
        }
        
        dp[1] = arr[1];
        if(n>=2) {
            dp[2] = arr[1]+arr[2];
        }
        
        for(int i=3;i<=n;i++) {
            dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
        }
        
        System.out.print(dp[n]);
        
        
    }
 
}