[BOJ] 2156번 : 포도주 시식

1. problem : 

https://www.acmicpc.net/problem/2156

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
int d[10005][3]; 
int a[10005];
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 

	for (int i = 1; i <= n; i++) cin >> a[i]; 

	d[1][1] = a[1];

	for (int i = 2; i <= n; i++) {
		d[i][0] = max({ d[i - 1][0],d[i - 1][1],d[i - 1][2] });
		d[i][1] = d[i - 1][0] + a[i];
		d[i][2] = d[i-1][1] + a[i];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max({ ans,d[i][0],d[i][1],d[i][2] });
	}
	std::cout << ans << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2156_1.cpp

basic-algo-lecture/0x10/solutions/2156_1.cpp at master · encrypted-def/basic-algo-lecture

dp를 이용해 풀어야 하는 문제다. 따라서, 세 가지 스텝을 따른다. 

첫 번째, 테이블을 정의한다. d [i][j] ( 0 <= j <= 2) d [i][0] --> 현재 포도주를 마시지 않는다. d [i][1] 현재 포도주를 마시고, 직전의 포도주를 마시지 않는다. d [i][2] 현재 포도주를 마시고 , 직전의 포도주도 마신다. 

두 번째, 점화식을 만든다. 

d [i][0] = max(d [i-1][0], d [i-1][1], d [i-1][2]) 

d [i][1] = d [i-1][0] + a [i]; 

d [i][2] = d [i-1][1] + a [i] ; 

 

세 번째, 초기값을 설정한다. 

여기서는 d [1][1]만 a [i]로 초기화하면 된다. 나머지는 0으로 초기화된다. 

 

3. solution 2: 

#include <bits/stdc++.h>
using namespace std;
int n; 
int d[10005]; 
int a[10005]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n; 
	for (int i = 1; i <= n; i++) cin >> a[i]; 

	d[1] = a[1]; 
	d[2] = a[1] + a[2]; 
	
	for (int i = 3; i <= n; i++) {
		d[i] = max({ d[i - 1],d[i - 2] + a[i],d[i - 3] + a[i - 1] + a[i] });
	}
	cout << d[n] << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2156.cpp

basic-algo-lecture/0x10/solutions/2156.cpp at master · encrypted-def/basic-algo-lecture

여기서는 일차원 배열로 테이블을 정의하고 있다. 따라서, d [i]는 i번째까지의 마신 포도주의 최댓값이다. 

d [i]는 다음과 같은 인자들로 max값을 결정한다. 

첫 번째, i번째 포도주를 마시지 않는다. 

두 번째, i번째 포도주를 마시고, i-2번째 포도주를 마신다. 

세 번째, i번째 포도주를 마시고, 직전의 포도주를 마신다. 

따라서, d [i] = max(d [i-1], d [i-2] + a [i] , d [i-3] + a [i-1] + a [i])로 정의된다.