[Programmers 코딩테스트 고득점 Kit] 도둑질

문제 링크입니다; https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

전형적인 DP 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 인접한 집을 털 수 없으므로 점화식은 다음과 같습니다. max(i번째 집 + (i - 2) 번째 집, (i - 1) 번째 집)

2. 1번에서 구한 점화식을 첫 번째 집 혹은 두 번째 집부터 적용이 가능합니다.

2.1 따라서, 첫 번째 집부터 적용한 점화식과 두 번째 집부터 적용한 점화식 중 더 큰 결과를 반환해줍니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int solution(vector<int> money) {
	vector<long long> startFromZero(money.size(), money[0]);
	vector<long long> startFromOne(money.size(), money[1]);
	for (int i = 2; i <= money.size() - 2; i++)
	{
	startFromZero[i] = max(startFromZero[i - 1], startFromZero[i - 2] + money[i]);
	}
	startFromOne[0] = 0;
	for (int i = 2; i <= money.size() - 1; i++)
	{
	startFromOne[i] = max(startFromOne[i - 1], startFromOne[i - 2] + money[i]);
	}
	return max(startFromZero[money.size() - 2], startFromOne[money.size() - 1]);
	}
	int main(void)
	{
	vector<int> money = { 1, 2, 3, 1 };
	cout << solution(money) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~