글 읽기 - dp배열로 풀었는데 어디가 틀린건지 모르겠어요

hdja1206 1년 전 0

혹시 점화식의 범위를 넓혀야 하나요? 제 머리로는 이게 최선인데ㅠㅠ

import java.util.*;
// import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] s = new int[n];
        for (int i = 0; i < n; i++) s[i] = sc.nextInt();

        int[] d = new int[n];
        d[0] = s[0];
        d[1] = s[0] + s[1];
        d[2] = Math.max(s[0] + s[2], s[1] + s[2]);
        for (int i = 3; i < n; i++) {
            d[i] = Math.max(d[i-3] + d[i-1]  + s[i], d[i-2]  + s[i]);
        }
        System.out.println(d[n-1]);
        

        sc.close();
    }
}

pmn0001 1년 전 0

음.. 우선은 16번 라인에서

d[i-3] + d[i-1] + s[i] 는

i - 3 번째 칸에서 얻을 수 있는 최대 점수에

i -1 번째 칸에서 얻을 수 있는 최대 점수를 더하기 때문에 생각보다 많은 점수를 더하게 될 것 같네요

거기에 추가적으로 손봐야할 것은

계단의 개수는 자연수라는 것을 생각하시면 될 거에요

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

문제

문제

출처

ICPC

dp배열로 풀었는데 어디가 틀린건지 모르겠어요

hdja1206 1년 전 0

pmn0001 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말