문제 이해 단계
https://www.acmicpc.net/problem/2579
입력으로 계단의 개수가 주어지고, 그다음부터 각 계단의 점수가 순서대로 주어진다.
출발부터 시작하여 마지막 계단까지 이동하는데 2가지 규칙을 따른다.
1. 이동은 1칸 또는 2칸을 이동한다.
2. 1칸을 이동할 때는 연속되는 3칸을 이동할 수 없다(1,2,3 이런 식)
이런 조건에서 마지막 칸까지 이동할 때
얻을 수 있는 최대 점수를 구하는 문제이다.
문제 접근 단계
마지막 계단을 무조건 밟아야 하기 때문에 마지막 계단부터 생각해 보자.
마지막 계단으로 도달할 수 있는 경우의 수는 2가지가 있다.
1. 1칸 이동했을 때
2. 2칸 이동했을 때
그런데 우리가 구해야 하는 것은 마지막 계단에 도착했을 때의 최대 점수이다.
때문에 두 경우 중, 점수가 더 높은 것을 선택해야 한다.
여기서의 점수는 여태까지 올라왔던 계단의 누적합이다.
마지막 계단에서부터 시작하면 처음 계단까지 또 계산해야 하는데,
그러면 시간초과가 뜰 가능성이 생긴다.
하여, 계산했던 값을 미리 저장해 두는 다이내믹 프로그래밍을 사용하기로 했다.
여기서 저장 배열은 2차원 배열을 이용하여
계단 별로 두 가지 상태를 따로 저장하게 해 두었다.
조건에서 연속적으로 두 번밖에 올라갈 수 없기 때문에,
두 개의 공간을 공간을 따로 마련하여 저장해 두었다.
이렇게 하여 재귀함수를 진행할 때 1칸씩 이동할 때는
check라는 매개변수를 두어 check+1을 하고,
2칸씩 이동할 때는 이 check를 1로 초기화해 준다.
그리고 재귀함수를 호출해 줄 때 check+1이 3이
1칸 이동하는 재귀함수를 호출하지 못하게 한다.
이런 과정을 반복하여 원하는 값을 구할 수 있게 된다.
그림으로 나타내보면 이렇게 된다.
dp(계단번호, check)라는 함수를 두고,
현재가 몇 번째 연속인지 체크하면서 재귀함수를 계속 호출한다.
이 과정을 시작지점(0)에 가까워질 때까지 반복하면 답을 구할 수 있다.
물론 이 과정에서
2차원배열에 누적합이 저장되기 때문에 연산속도가 줄어든다.
자세한 것은 코드를 통해 설명하겠다.
문제 구현 단계
long long int d[301][3];
int stair[301];
long long int dp(int x, int check) {
if (x == 1) return d[x][check] = stair[x];
if (x <= 0) return 0;
if (d[x][check] != 0) return d[x][check];
long long int v = 0;
if (check + 1 < 3 || x -1 == 0) v = max(v, stair[x]+ dp(x - 1, check + 1));
v = max(v, stair[x] + dp(x - 2, 1));
return d[x][check] = v;
}핵심이 되는 dp함수이다.
매개변수로 계단 번호와 check를 받는다.
위에 있는 d라는 2차원 배열은
앞서 설명했던 누적합을 저장해 두기 위한 배열이다.
2차원을 3으로 설정한 이유는 인덱스를 1부터 쓰기 위함이다.
굳이 long long int로 한 이유는 불필요한 오버플로우를 막기 위함이다.
일단 초기 설정으로 첫 번째 계단인 경우에는 바로 그 계단점수를 반환해 주고
시작지점이거나 x값이 그거보다 작은 경우에는 더 이상의 함수 계산을 막는다.
그리고 2차원 배열의 이미 저장된 값이 있다면
불필요한 연산을 하지 않고 바로 그 값을 반환한다.
가장 중요한 밑에 부분인데, check+1이 3을 넘지 않을 때
즉, 연속 3칸씩 움직이지 않았을 때만, 1칸씩 이동하는 재귀함수를 호출한다.
이때 자기 자신의 점수를 더해줘 누적합을 완성해 준다.
여기서 x-1 == 0을 예외처리해 준 이유는
시작점에서 움직이는 것은 연속적인 움직임으로 치지 않기 때문에
예외적으로 1칸 이동을 하게 해주는 것이다.
그리고 밑에서 2칸씩 움직이는 재귀함수를 호출해 주는데,
이때 check는 1로 초기화해 준다.
이 두 값을 비교해 더 큰 값을 해당 d [x][check]의 값으로 지정한다.
위 과정을 계속 반복한다.
위 함수 빼고는 딱히 설명할 부분이 없으므로 전체 코드를 올리고 설명을 끝내겠다.
#include <iostream>
using namespace std;
long long int d[301][3];
int stair[301];
long long int dp(int x, int check) {
if (x == 1) return d[x][check] = stair[x];
if (x <= 0) return 0;
if (d[x][check] != 0) return d[x][check];
long long int v = 0;
if (check + 1 < 3 || x -1 == 0) v = max(v, stair[x]+ dp(x - 1, check + 1));
v = max(v, stair[x] + dp(x - 2, 1));
return d[x][check] = v;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int n, score;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> score;
stair[i] = score;
}
cout << dp(6, 1);
}
시행착오
프로젝트 때문에 바빠서 알고리즘을 오랜만에 풀어봤는데 역시 막히더라.
이 문제는 저장되는 배열을 2차원으로 써야 한다는 발상을
생각하는 게 어려워서 푸는데 오래 걸렸다.
게다가 생각한다고 해도 이를 이용하여 재귀함수를 만드는 것이 어려웠다.
이런 류의 문제를 많이 풀어봐야 할 것 같다.