2579 : 계단 오르기

네르기·2021년 9월 6일

동적 프로그래밍 생각

알고리즘

목록 보기

48/76

어떤 문제인가?

특정 조건을 만족하면서 동적 프로그래밍을 이용해 최댓값을 구하는 문제.

시행착오 횟수

1번

관찰

두 계단씩 오르거나 한 계단씩 오르거나. 그러나 연속으로 3계단을 한 칸씩 오르는 일이 없도록 해야 한다. 조건을 찾아야 풀 수 있다.
마지막 계단은 반드시 밟아야 한다. 이를 이용해 거꾸로도 풀 수 있다.
그리디 알고리즘이 적용되지 않는다. 모든 경우를 탐색해야 한다.

1차 시도 : 구상

다음과 같은 식을 떠올렸지만, 조건에 들어맞지 않았다.
$D_{l}$ 은 $l$ 번째 계단에서의 최대 점수 누적합이며,
$S_{l}$ 은 $l$ 번째 계단에 부여된 점수이다.

D_{l} = max(S_{l}+D_{l-1}, S_{l}+D_{l-2})

이때 가장 어려움을 겪었던 부분은 '어떻게 해야 3계단을 연속으로 올라갔는지를 표현할 수 있는가?'였다.

2차 시도 : AC

2차원 배열 $D_{ij}$ 를 정의했다. $i$ 번째 계단에서 $j$ 번째 계단으로 올라갈 때 점수의 누적합이다.
즉, $D_{12}$ 는 1번째 계단에서 2번째 계단으로 올라갈 때 그동안 쌓인 점수를 의미한다.

이를 이용하면 3계단을 연속으로 오르는 경우를 배제할 수 있게 된다. 다음과 같은 예시를 들겠다.

D_{23} = D_{02}+S_{3} \\ D_{23} = D_{12} + S_{3}

$D_{12}$ 와 $D_{23}$ 을 보면, 위 정의에 따라 각각 1->2번째와 2->3번째 계단을 오를 때 점수의 누적합을 나타낸다. 그러나 1,2,3번 계단을 순서대로 한 계단씩 오르는 것은 조건에 어긋난다.

일반화하여 수식으로 나타내면 조건을 어기는 경우는 다음과 같다.

k-i=1 \iff k=i+1

위 성질을 이용하여, 아래와 같은 식을 세웠다.
다음 식은 $i \geq 2$ 인 경우에 유효하다.

D_{ik} = \begin{cases} max(D_{(i-1)i}+S_{k}, D_{(i-2)i}+S_{k}) & (k \neq i+1) \\ D_{(i-2)i}+S_{k} & (k = i+1) \end{cases}

$i$ 가 각각 $0, 1$ 일 때의 식이다.

\begin{cases} D_{1k} = D_{01}+S_{k} & (i=1) \\ D_{0k} = S_{k} & (i=0) \end{cases}

이를 코드로 나타내었다.

#include <stdio.h>
#define max(x, y) x>y?x:y

int D[300][300], S[301];

int main()
{
	int N,i,j;
	scanf("%d", &N);
	for(i=1;i<=N;i++) scanf("%d",S+i);
	for(i=0;i<N;i++) {
		for(j=i+1;j<i+3;j++) {
			if(i==0) D[0][j]=S[j];
			else if(i==1) D[1][j]=D[0][1]+S[j];
			else {
				if(j-i==1) D[i][j]=D[i-2][i]+S[j];
				else D[i][j]=max(D[i-1][i]+S[j],D[i-2][i]+S[j]);
			}
		}
	}
	printf("%d",max(D[j-4][j-2],D[j-3][j-2]));
}

다른 분들의 풀이

내 풀이는 좀 장황하다. 정석은 다음과 같았다.

D_{n} = max(D_{n-2}+S_{n},\;D_{n-3}+D_{n-1}+S_{n}) \qquad (n>3)

다른 분들께서 올리신 훌륭한 풀이를 참고하였다.
내가 좀 어렵게 생각한 것 같다. 위처럼 쉽게 표현이 가능하다는 걸 이제 알았다.

#include <stdio.h>

int a[301], d[301];
int max(int x, int y) { if (x>y) return x; return y;}
int dfs(int n){
  if(n<=0) return 0;
  if (d[n]) return d[n];
  return d[n]=max(dfs(n-2)+a[n],dfs(n-3)+a[n-1]+a[n]);
}

int main(){
  int n;
  scanf("%d", &n);
  for (int i=1; i<=n; i++) scanf("%d", &a[i]);
  printf("%d\n", dfs(n));
}

gaelim님 소스
-> https://www.acmicpc.net/source/7062879

특이한 풀이로, 배열을 전혀 쓰지 않고 7개의 변수만으로 해결한 풀이도 있었다.

#include<stdio.h>

int main()
{
	int N,a1,a2,b1,b2=0,c1=0,c2=0,x;

	scanf("%d",&N);
	N--;

	scanf("%d",&b1);

	while(N--)
	{
		scanf("%d",&x);
		a1=c1>c2?c1:c2;
		a2=b1;
		c1=b1;
		c2=b2;
		b1=a1+x;
		b2=a2+x;
	}
	
	printf("%d",b1>b2?b1:b2);
}