[백준 - 2156] 포도주 시식

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001][4] = {0,};
int arr[10'001] = {0,};

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);

	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	//2. Set initial value
	dp[1][1] = dp[1][0] = 0;
	dp[1][2] = dp[1][3] = arr[1];

	for (int i = 2; i <= n; ++i)
	{
		dp[i][0] = max(dp[i - 1][2], dp[i - 1][3]);
		dp[i][1] = dp[i - 1][0];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i];
		dp[i][3] = dp[i - 1][2] + arr[i];
	}

	//3. Print
	cout << max(max(dp[n][0], dp[n][1]), max(dp[n][2], dp[n][3]));
	return 0;
}

---

||사고 과정

비슷한 문제를 좀 풀어서 풀이방법은 어렵지 않게 생각 할 수 있었다.

다만 나는 이차원 테이블을 사용하여 좀 어렵게 풀었다.

 

이번에도 그냥 감으로 이차원 테이블로 사용했던것 같다.

그래서 dp[ i ][ j ]에서 [ j ]의 경우를 찾으려고 하니까 처음에는 3개가 나왔다.

1번 쉬는 경우, 1번째로 마시는 경우, 2번째로 마시는 경우

 

사실 2번 쉬는 경우가 포함되어야 하지만 나는 최대로 마실거니까 1번만 쉬어도 되지 않을까 라는 생각을 했다.ㅠ

그래서 처음에 틀렸다가 예외를 찾고 추가하여 정답을 맞췄다.

---

||사용 기법

• DP

---

||풀면서 느낀 것

• 테이블을 이차원으로 사용하는 것을 잘 생각해서 설정해야겠다.

요새 이차원으로 DP를 풀다보니 이것도 당연히 이차원일꺼라는 안일한 생각이 있었다ㅠㅠ

감으로 풀지말고 확실한 논리로 테이블을 세팅하자ㅠ

• 이런 문제는 뭔가 어차피 안해도 돼~ 라는 예외가 있는것 같다.

어떠한 경우는 생각해야하지 않을까? 하면 어차피 안해도 되는 예외같은게 많았다.

나는 이 문제에서 i번째 포도주를 안마시고 dp[i - 2]가 최대값일 수도 있지 않나? 라는 생각이 있었는데

필요 없는 예외였다.

다음에는 예외를 좀 더 논리적으로 제거해가야겠다.

---

||나아 진것

• 예외 생각

다른 사람것을 보지 않고 잘 생각했음

 

---

||더 나은 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001] = { 0, };
int arr[10'001] = { 0, };

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);

	int n; cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	//2. Set initial value
	dp[1] = arr[1];
	dp[2] = arr[2] + arr[1];

	for (int i = 3; i <= n; ++i)
	{
		dp[i] = max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i];
		dp[i] = max(dp[i - 1], dp[i]);
	}

	//3. Print
	cout << dp[n];
	return 0;
}

일차원 테이블로 풀이하는 방법이다.

dp[ i ]는 i번째 포도주에 왔을 때 최대로 마실 수 있는 양을 지닌다.

그 양의 경우의 수는 세가지인데

1) i번째를 두번째로 마시는 경우,

이는 i - 3의 최대 값과 arr[ i - 1 ]을 더해주면 arr[ i ]가 알아서 두번째로 마시는게 된다.

 

2)i번째를 첫번째로 마시는 경우,

이는 i - 1을 안마신경우이므로 dp[ i - 2 ]에서 현재 arr [ i ]을 더해주면 된다.

 

3)i번째를 안마시는 경우,

당연히 dp[i - 1] 이다.

dp[i - 2]라는 선택지도 있을것같지만 잘 생각해보면 dp[i - 2] <= dp[i - 1] 가 될 수 밖에 없다.