[BOJ/C#] 2579 계단오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

using System;
using System.Collections.Generic;
using System.IO;
using System.IO.Pipes;
using System.Linq;
using System.Text;

namespace BOJ_9095
{
    class Program
    {
        static void Main(string[] args)
        {
            //abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
            StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            //런타임 에러 (IndexOutOfRange)
            //계단의 개수는 300이하의 자연수
            const int MAX = 301;    //0은 버리고 1부터 쓸거라 
            
            //입력
            int n = int.Parse(sr.ReadLine());   

            int[] arr = new int[MAX];
            int[] dp = new int[MAX];

            for (int i = 1; i <= n; i++)
                arr[i] = int.Parse(sr.ReadLine());
       
            //1  2  3  4  5  6 
            //10 20 15 25 10 20 
            
            //문제 해결
            dp[0] = 0;
            dp[1] = arr[1];
            dp[2] = arr[1] + arr[2];
            
            //주의: 3번째 계단은 비교 해야 함 아래와 같이 고정 아님  
            //dp[3] = arr[3] + arr[2]; 
            
            // Console.Clear();
            
            // sw.WriteLine(dp[1]);    //10
            // sw.WriteLine(dp[2]);    //30
            // sw.WriteLine(dp[3]);    //35

            
            for (int i = 3; i <= n; i++)
            {
                
                dp[i] = Math.Max(
                    arr[i] + arr[i-1] + dp[i-3],    //dp[i-3] 요부분 주의 (이전까지는계산된었음으로 dp테이블 사용)
                    arr[i] + dp[i-2]); 
            }
            
            // sw.WriteLine(dp[4]);    //10
            // sw.WriteLine(dp[5]);    //55
            // sw.WriteLine(dp[6]);    //75
            
            sw.WriteLine(dp[n]);

            sr.Close();
            sw.Close();
        }
    }
}