[EPPER] 13회 9번

문제

 

---

풀이

 

동적계획법 문제의 수많은 유형 중 하나이다. 이런류의 문제를 처음 봤다면 어렵겠지만, 몇 개 풀어보고 나면 그 문제가 그 문제라 원활하게 풀 수 있다. 각 index에서의 최댓값을 m_max에 저장한다. 그럼 이제 m_max에 값이 어떻게 들어가는지 살펴보겠다.

 

m_max[1] : 돈이 1개라면 그냥 그걸 주워가면 된다. 그러므로 m_max[1] = m[1]

m_max[2] : 돈이 2개여도 그걸 다 주워간다 해서 규칙을 어기진 않는다. 그러므로 m_max[2] = m[1] + m[2]

m_max[3] : 돈이 3개라면 이제 모든 돈을 주워갈 수는 없다. 3개 중 금액이 가장 커질 수 있는 2장을 가져가자.

               (근데 코드는 왜 [1]+[2]를 까먹었지? 실수한 것 같다.)

 

m_max[n] (n>3) 부터는 3가지 경우 중 가장 큰 값을 가져오면 된다.

1. m_max[n-1] (n번째 돈을 가져가지 않음)

2. m[i] + m[i-1] + m_max[i-3] (n-2번째 돈을 가져가지 않음)

3. m[i] + m_max[i-2] (n-1번째 돈을 가져가지 않음)

 

사실 m_max[3]도 그냥 바로 함수에 넣을 수 있다. input을 index 1부터 받았기 때문이다. m[0]이 있기 때문이다. 저 코드를 작성할 당시에는 아직 이런 문제가 익숙하지 않아서 이런 잔실수들을 한 것 같다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int m[30001];
int m_max[30001];

int max(int a, int b) {
	if (a > b)
		return a;
	else
		return b;
}

void find_max(int num) {
	if (num <= 3)
		return;
	for (int i = 4; i <= num; i++) {
		m_max[i] = max(m_max[i - 1], max(m[i] + m[i - 1] + m_max[i - 3], m[i] + m_max[i - 2]));
	}
}

int main() { 
	int n;

	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &m[i]);
	m_max[1] = m[1];
	m_max[2] = m[2] + m[1];
	m_max[3] = max(m[1] + m[3], m[2] + m[3]);
	find_max(n);
	printf("%d", m_max[n]);
}