<Beakjoon> Dynamic Programming_#2579 계단 오르기 #2156 포도주 시식 c++

Google 아니고 Joogle·2022년 3월 9일
0

Baekjoon

목록 보기
35/47
post-thumbnail

#2579 계단 오르기
#2156 포도주 시식

마지막 계단/포도주를 골라야 한다는 조건 빼고는 본질적으로 동일한 문제다
이 문제를 정확하게 이해하는데 이틀이 걸렸다..

계단 오르기를 예시로 들면

dp[i]=i번째 계단을 밟았을 때 얻을 수 있는 최대 점수로 두고 점화식을 도출해본다
(각 계단에 적혀있는 점수는 stairs[] 배열에 저장되어 있다)

e.g.
starts[]={10,20,15,25,10,20} 이고 1번 째부터 저장되어 있다

dp[1]=10
dp[2]=10+20

dp[1]와 dp[2]는 자명하다

dp[3]= 10+15 / 20+15 => 20+15

3번 연속 계단을 밟을 수 없다는 조건 때문에 dp[3]부터는 생각을 해보아야 한다.

i번째 계단에 와서 밟았을 때, i-1번째 계단을 밟는 것과, i-2번째 계단을 밟는 경우로 생각할 수 있다.

그렇다면 점화식이
dp[i]=max(dp[i-1], dp[i-2])+staris[i] 인가? 아니다


위의 그림과 같이 ⓐ,ⓑ 두 경우로 나타낼 수 있다

ⓑ 에서는 i-2이 선택되지 않았다. dp[i-3] (i-3번째까지 밟았을 때 얻을 수 있는 최대 이익)에 이전 계단, 현재 계단을 밟은 값을 더해준다.

(dp[i-1]에 저장된 값이 i-2를 밟고 얻은 최적해인지 i-2를 밟지 않고 얻은 최적해인지는 모른다)

dp[i-3]에 staris[i-1]과 staris[i]를 더해준다

ⓐ 에서는 i-2가 선택되었다. 즉 i-2를 고른다는 뜻은 i-2지점에서 얻을 수 있는 최대점수 dp[i-2]를 고른다는 뜻이다.

따라서 ⓐ의 경우는 dp[i-2]+staris[i] 이다.

전체코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 301;

int N;
vector<int> stairs;
int cache[MAX];

void dp() {
	cache[1] = stairs[1];
	cache[2] = stairs[1] + stairs[2];

	for (int i = 3; i <= N; i++)
		cache[i] = max(cache[i - 3] + stairs[i - 1] + stairs[i],
			cache[i - 2] + stairs[i]);
	cout << cache[N] << endl;
}

void input() {
	cin >> N;
	stairs = vector<int>(N+1);

	for (int i = 1; i <= N; i++)
		cin >> stairs[i];
}

int main() {
	input();
	dp();
	return 0;
}

다음으로 포도주 시식의 경우, 마지막 포도주를 꼭 마셔야한다는 내용이 없다. 따라서 위에서 max값을 비교할 때, dp[N-1]의 경우를 하나 더 추가해준다.

전체코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> glass;
vector<int> dp;

void solution() {
	dp[0] = 0;
	dp[1] = glass[1];
	dp[2] = glass[1]+glass[2];

	for (int i = 3; i <= N; i++) {
		dp[i] = max({ dp[i - 2] + glass[i], 
			dp[i - 3] + glass[i - 1] + glass[i],
			dp[i - 1] });
	}
	cout << dp[N] << endl;
}

void input() {
	cin >> N;
	glass = vector<int>(N+1);
	dp = vector<int>(N + 1);

	for (int i = 1; i <= N; i++)
		cin >> glass[i];
}

int main() {
	input();
	solution();

	return 0;
}
profile
Backend 개발자 지망생

0개의 댓글