이래저래 좀 고생을 한 문제이다.

역시 좀 DP 쪽에서 약하다는 점을 다시 확인한 것 같다.

(정확하게는 DP라기보다는 점화식을 이끌어내는 부분이 약하다;;; -_-)


다른 사람들의 힌트를 보기도 했는데 왜 틀릴까? 했는데, 알고보니 return을 넣지를 않는 어처구니 없는 실수를 하고 있었다;;; -_-



#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

int drinkWine(int &nCount, int *pArrWine)
{
	int nRet = 0;

	switch (nCount)
	{
	case 0:
		return 0;
	case 1:
		return pArrWine[0];
	case 2:
		return (pArrWine[0] + pArrWine[1]);
	case 3:
		return max(pArrWine[0] + pArrWine[1], pArrWine[1] + pArrWine[2]);
	default:
		int *pBuf = (int *)malloc(sizeof(int) * nCount);
		if (pBuf != nullptr)
		{
			pBuf[0] = pArrWine[0];
			pBuf[1] = pArrWine[0] + pArrWine[1];
			pBuf[2] = max(pBuf[1], max(pArrWine[1] + pArrWine[2], pArrWine[0] + pArrWine[2]));

			for (int i = 3; i < nCount; ++i)
				pBuf[i] = max(pBuf[i - 1], max(pBuf[i - 3] + pArrWine[i - 1] + pArrWine[i], pBuf[i - 2] + pArrWine[i]));

			nRet = pBuf[nCount - 1];

			free(pBuf);
		}
		break;
	}

	return nRet;
}

int main()
{
	int nCount = 0;
	scanf("%d", &nCount);

	int *pArray = (int *)malloc(sizeof(int) * nCount);
	if (pArray != nullptr)
	{
		for (int i = 0; i < nCount; ++i)
			scanf("%d", &pArray[i]);

		printf("%d\n", drinkWine(nCount, pArray));

		free(pArray);
		pArray = nullptr;
	}

    return 0;
}



백준은 다른건 좋은데 틀렸을때, input은 무엇이었고, 예상 output은 무엇인지를 알려주지 않아서 틀린 이유를 찾는게 좀 막막한 것 같다.

(확실히 이 부분은 leetcode가 좋지만, 백준은 약간 서술형 문제라는 특징이 있어서 그건 장점이다)

'Programming > C,C++' 카테고리의 다른 글

[BOJ] 2165. 포도주 시식  (0) 16:00:07
[LeetCode] 34. Search for a Range  (0) 2018.01.26
[LeetCode] 33. Search in Rotated Sorted Array  (0) 2018.01.26
[LeetCode] 22. Generate Parentheses  (0) 2018.01.25
[BOJ] 10844. 쉬운 계단 수  (0) 2018.01.21
[BOJ] 1149. RGB거리  (0) 2018.01.20

+ Recent posts