C프로그램으로 알고리즘을 공부하고 있는 학생입니다. (Github)
이번 문제는 간단한 DP 문제입니다.
이 문제를 해결하기 위해 DP Top-Down 방식(재귀함수)을 선택했고, 메모이제이션을 통해서 문제에서 알려준 조건 그대로 함수를 만들었습니다.
조건은 이렇습니다.
- 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
- 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
- 마지막 도착 계단은 반드시 밟아야 한다.
- 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
그래서 저는 한계단씩 이동을 하면서 두번째 이전 계단과 바로 직전 계단을 밟았는지 안밟았는지 확인하면서 최대값을 찾아가면서 풀면 되겠다고 판단했습니다.
#include <stdio.h>
#include <string.h>
#define MAX_HIGHT 301
#define TRUE 1
#define FALSE 0
int steps[MAX_HIGHT];
int check[MAX_HIGHT];
int memo[MAX_HIGHT][2][2];
int MaxPoint(int idx, int N) {
// 이번 계단을 밟았을때 최대값, 밟지 않았을때 최대값
int ThisStep, NotThisStep;
// 두번째 전과 바로 직전 계단을 밟았는지 않았는지 저장하는 변수
int two_before = (idx >= 2)? check[idx - 2] : FALSE;
int one_before = (idx >= 1)? check[idx - 1] : FALSE;
if(idx == N) {
// 마지막 계단은 항상 밟아야 함으로 만약 마지막 계단을 밟을 수 없는 경우 -10000을 시켜 Max값이 될 수 없게 한다.
if(idx > 1 && two_before && one_before){
return -10000;
}
return steps[N];
}
// 답이 있다면 그 답을 이용 (Memoization)
if(memo[idx][two_before][one_before] != -1)
return memo[idx][two_before][one_before];
// 이전 계단 두개를 모두 밟았을때(연속된 계단 3번 밟으면 안되기 때문에)
if(idx > 1 && two_before && one_before) {
check[idx] = FALSE;
return memo[idx][two_before][one_before] = MaxPoint(idx + 1, N);
}
// 두번째 이전 계단을 밟았지만 바로 이전 계단을 밟지 않았을때
if(idx > 1 && two_before && !one_before) {
check[idx] = TRUE;
return memo[idx][two_before][one_before] = MaxPoint(idx + 1, N) + steps[idx];
}
// 만약 1번째 계단을 밟지 않았다면 2번째 계단 밟아햐함
if(idx == 1 && check[idx-1] == FALSE) {
check[idx] = TRUE;
return memo[idx][two_before][one_before] = MaxPoint(idx + 1, N) + steps[idx];
}
// 나머지 경우 이 계단을 밟을 때, 안 밟을 때 비교
check[idx] = FALSE;
NotThisStep = MaxPoint(idx + 1, N);
check[idx] = TRUE;
ThisStep = MaxPoint(idx + 1, N) + steps[idx];
return memo[idx][two_before][one_before] = (ThisStep > NotThisStep)? ThisStep : NotThisStep;
}
int main(void) {
int N;
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", &steps[i]);
memset(memo, -1, sizeof(memo));
memset(check, FALSE, sizeof(check));
printf("%d\n", MaxPoint(0, N - 1));
return 0;
}
제가 코드를 짤 때는 저 나름대로 문제의 조건대로 예외 처리를 하면서 작성하였기 때문에 작성하는 시간이 오래 걸리지는 않았지만, 코드를 작성하고 다시 보니 코드가 길어져서 난잡해 보이고 남들이 봤을 때 이해하는 데 오래 걸리겠다고 생각이 들었습니다.
문제 해결 후 다른 분들의 소스코드를 보니 Bottom-Up 방식을 이용한다면 훨씬 더 간단하면서 빠르게 문제를 해결 할 수 있다는 것을 알았습니다.
#include <stdio.h>
#define max(a, b) ((a) > (b)? (a): (b))
int S[301], D[301];
int main() {
int stair;
scanf("%d", &stair);
for (int i = 1; i <= stair; i++)
scanf("%d", S + i);
D[1] = S[1], D[2] = S[1] + S[2];
for (int i = 3; i <= stair; i++)
D[i] = max(S[i] + D[i - 2], S[i] + S[i - 1] + D[i - 3]);
printf("%d\n", D[stair]);
}
Bottom-Up 방식으로 문제를 해결한다면
D[i]의 답은
(마지막 계단 값(S[i])와 이전 두번째 계단을 밟은 경우(D[i-2])을 더한 경우) 와
(마지막 계단 값(S[i])와 바로 직전 계단 (s[i-1])와 이전 세번째 계단을 밟은 경우(D[i-3]))를
비교해서 더 큰 값이 답이 된다는 논리로 간단하게 해결했습니다.
Check
- #define max(a, b) ((a) > (b)? (a): (b)) 와 같이 간단한 함수는 #define 을 활용해 한줄로 작성이 가능하며 선행처리기에 의해서 처리되기 때문에 속도가 훨씬 빠르다.
- 나는 문제에 나온 그대로 직관적으로 생각하려고 하는 경향이 있다(
재귀를 이용하는 것도). Top-Down 코딩하는 사람에게는 방식은 직관적이라는 장점이 있지만 사람에게 직관적이라면 그만큼 컴퓨터에는 처리할게 많다는 것을 명심하자. Bottom-Up 방식은 조금 더 생각을 할 필요가 있지만 훨씬 빠르고 코드가 간단해질 수 있다.
Handong University student.