[C언어] 백준 2156 : 포도주 시식

생각의 흐름

이거 했었다. 계단오르기 확장이다.

• 조건은 쉽다. 3잔연속만 안마시면 된다.

• 4잔을 기준잡고, 점화식을 찾아보자. a,b,c,d가 있다.
  OOXO, OXOO, XOOX, OXOX, XOXO 이렇게 있다. 2번연속으로 안마시는건 최대값이 절대 안나오기때문에 고려안했다. 근데 위에서도 OOXO랑 XOXO를 비교해보면 OOXO가 항상 이기기에, XOXO를 버리고 OXOX도 같은 논리로 버린다. 결국 3개가 남는다.

• OOXO, OXOO, XOOX 3가지 경우를 계산해주고, 최대값을 구해버리면 끝난다.

• OOXO -> dp[i - 2] + input[i]

• OXOO -> dp[i - 3] + input[i] + input[i - 1]

• XOOX -> dp[i - 1]

• 3가지 경우 다 점화식으로 바꿔주었고, 최대값을 구해 그걸 dp[i]에 저장해버리면 끝.

#include <stdio.h>

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

int main()
{
	int i, n;
	int dp[10001];
	int input[10001];
	scanf("%d", &n);
	i = 1;
	while (i <= n)
	{
		scanf("%d", &input[i]);
		i++;
	}
	dp[1] = input[1];
	dp[2] = input[1] + input[2];
	i = 3;
	while (i <= n)
	{
		dp[i] = max(dp[i - 2] + input[i], dp[i - 3] + input[i] + input[i - 1], dp[i - 1]);
		i++;
	}
	printf("%d", dp[n]);
}

다른 사람들도 내 논리와 같다. 코드도 거의 유사하다.
아 대신 max를 나처럼 3가지경우 말고, 그냥 define으로 a b 그거로 하고, dp[i]구할때 그 max를 두번사용해서 더 깔끔하다.