(16) [C++, Java] 백준 No.2579 : 계단 오르기

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-17-DP-문제-풀이3-6-백준-No2579-계단-오르기

 

# C++(2차원 배열)

#include<iostream>

using namespace std;

int a[301];
int d[301][3];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    d[1][1] = a[1];
    d[1][2] = 0;

    d[2][1] = a[2];
    d[2][2] = a[1] + a[2];

    for (int i = 3; i <= n; i++){
        d[i][1] = max(d[i-2][1], d[i-2][2]) + a[i];
        d[i][2] = d[i-1][1] + a[i];
    }

    cout << max(d[n][1], d[n][2]) << "\n";
}

 

# Java(2차원 배열)

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
        int[][] d = new int[n+1][3];
        d[1][1] = a[1];
        for (int i=2; i<=n; i++) {
            d[i][2] = d[i-1][1] + a[i];
            d[i][1] = Math.max(d[i-2][1], d[i-2][2]) + a[i];
        }
        System.out.println(Math.max(d[n][1], d[n][2]));
    }
}

 

# C++(1차원 배열)

#include <stdio.h>
#define max(a,b) (((a)>(b))?(a):(b))
int a[301];
int d[301];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    d[1] = a[1];
    d[2] = a[1]+a[2];
    for (int i=3; i<=n; i++) {
        d[i] = max(d[i-2]+a[i], d[i-3]+a[i]+a[i-1]);
    }
    printf("%d\n",d[n]);
    return 0;
}

 

# Java(1차원 배열)

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
        int[] d = new int[n+1];
        d[1] = a[1];
        d[2] = a[1]+a[2];
        for (int i=3; i<=n; i++) {
            d[i] = Math.max(d[i-2]+a[i], d[i-3]+a[i-1]+a[i]);
        }
        System.out.println(d[n]);
    }
}