[C#] 백준 2579번 문제풀이

문제번호: 2579

문제명: 계단 오르기

문제링크: https://www.acmicpc.net/problem/2579

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

해당 문제는 계단 오르기를 통한 점수 획득의 최대치를 구하는 문제입니다.

이번 문제는 생각이 부족했던 탓인지 아직은 벅찬 문제였었던건지 모르겠지만 약 1시간정도 고민해본 끝에 도무지 좋은 방법이 생각나질 않아서 강의영상을 참고한 점 양해 부탁드립니다.
강의링크: https://www.youtube.com/watch?v=VA0yKXI80rg

 

위 강의를 시청 후 코드를 작성하기 시작했습니다. dp테이블을 1차원으로 만들어둔 후, dp테이블을 반복문i로 채워가기 시작합니다.

계단을 오를때는 두가지 경우의 수가 있습니다. OXO로 밟거나, XOO로 밟거나. 이 두 경우의 수중 더 큰 값을 dp에 채워줍니다.

다음에는 좀 더 쉬운 다이나믹 프로그래밍 문제를 풀어봐야겠습니다.

다음은 정답코드입니다.

public static void Main()
{
    int N = int.Parse(Console.ReadLine());
    int[] lst = new int[N + 1];
    for (int i = 1; i <= N; i++)
        lst[i] = int.Parse(Console.ReadLine());

    if (N == 1)
    {
        Console.WriteLine(lst[1]);
        return;
    }

    int[] dp = new int[N + 1];
    dp[1] = lst[1];
    dp[2] = lst[1] + lst[2];

    for (int i = 3; i <= N; i++)
    {
        dp[i] = Math.Max(dp[i - 2] + lst[i], dp[i - 3] + lst[i - 1] + lst[i]);
    }

    Console.WriteLine(dp[N]);
}