BOJ) 2579 계단 오르기 <C++>

백준 2579 계단 오르기 <C++>

www.acmicpc.net/problem/2579

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

이번 문제의 가장 큰 핵심은 아래의 규칙을 지키는 것이다.

• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다.
• 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
• 마지막 도착 계단은 반드시 밟아야 한다.

 

이 문제를 접근할 때 처음에는 가장 뒤의 칸에서부터 시작했다. 마지막 도착 계단을 반드시 밟아야 한다는 조건 때문이었다.

예를 들어 위 사진의 가장 마지막 칸인 "20"부터 시작해서 N - 1 번째칸과(여기서 N은 현재 위치라고 생각하겠다.) N - 2 번째 칸 중에 값이 큰 칸으로 이동한다.

• N - 1 칸으로 이동했다면 N - 2칸을 0으로 만든 후 인덱스를 N - 1로 옮기고 다시 루프를 돈다.
• N - 2칸으로 이동했다면 인덱스를 N - 2로 옮기고 다시 루프를 돈다.

 

이런 식으로 시작 지점까지 도착했을 경우에 결과를 계산했다.

하지만 이 경우에는 시작점을 1번 칸부터 시작했을 때, 2번 칸부터 시작했을 때의 경우를 고려하지 못했다.

로직

위의 방법이 실패하고 다시 앞에서부터 결과를 저장하기로 하였다.

일단 처음에 시작할 수 있는 경우들을 저장해 두었다. 우리는 계단을 1칸 혹은 2칸을 오를 수 있기 때문에 2칸을 이동하는 기준으로 모든 경우를 저장해두었다.

점수[1] = 계단[1]

점수[2] = 계단[1] + 계단[2]

이제 여기서 3번째 칸으로 이동할 때 고민이 발생한다. 3번째 칸을 가기 위해선 1번 혹은 2번 계단을 무조건 밟아야 한다.

그렇다면 계단 3을 밟았을 때의 점수는 아래 두 개의 경우 중 하나이다.

• 점수[3] = 계단[3] + 계단[1]
• 점수[3] = 계단[3] + 계단[2]

 

하지만 이렇게 계산한다면 우리는 점수 배열에서 누적된 값을 저장하는 것이 아니라 이전 값들만 저장하게 된다. 따라서 우리는 앞서 구해두었던 N - 1번 계단과 N - 2번 계단의 누적 값을 더할 것이다.

• 점수[3] = 계단[3] + 점수[1]
• 점수[3] = 계단[3] + 점수[2]

 

하지만 아래 점수[2] 우리가 계단[1]과 계단[2]을 모두 밟는 것으로 정해두었다. *그렇다면 아래와 같은 경우에는 계단을 3번 연속 밟게 되어버린다!! *이 문제를 해결하기 위해 점수[2]를 더한 경우는 원래대로 돌리기로 하였다.

• 점수[3] = 계단[3] + 계단[2]

 

그럼 마찬가지로 누적된 값을 못 받아 오기 때문에 여기서 특별한 방법을 하나 적용할 것이다. 우리는 무조건 1, 2칸만 움직일 수 있고 3칸 연속 밟을 수 없기 때문에 2번 계단과 3번 계단을 밟았다면 무조건 0번에서 출발해야 한다는 것이다!

즉, N번과 N -1번 계단을 밟았다면 그 전에는 무조건!! N - 3을 밟은 상태에서 출발하여야 한다. 따라서 우린 위의 식을 아래와 같이 변경할 수 있다.

• 점수[3] = 계단[3] + 계단[2] + 점수[0]

 

이제 두 식을 일반화시켜보면 아래와 같다.

• 점수[N] = 계단[N] + 점수[N - 2]
• 점수[N] = 계단[N] + 계단[N - 1] + 점수[N - 3]

 

그렇다면 N번째 계단에서의 최대 점수 값은 두 값 중에 큰 값을 구하면 된다.

카테고리

• DP(Dynamic Programing)

코드

#include <iostream>
#include <vector>

std::vector<int> dp_vector;
std::vector<int> points;
int cnt;


void output()
{
    std::cout << dp_vector[cnt];
}

void solution()
{
    dp_vector[1] = points[1];
    dp_vector[2] = points[2] + points[1];
    for (int i = 3; i <= cnt ; i++)
    {
        dp_vector[i] = points[i] + std::max(dp_vector[i - 2], dp_vector[i - 3] + points[i - 1]);
    }
}

void input()
{
    std::cin >> cnt;
    points.resize(cnt + 1);
    dp_vector = std::vector<int>(cnt + 1, 0);
    for (int i = 1 ; i <= cnt ; i++)
        std::cin >> points[i];
}

void preset()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}

int main()
{
    preset();
    input();
    solution();
    output();
}