[프로그래머스] 도둑질 (C++, Java)

www.welcomekakao.com/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

문제설명

 

간단히 인접하지 않은 두 집을 털어 max 값을 구해주는 문제이다.

 

점화식

• 첫번째 집부터 터는 경우 = 마지막 집 선택의 경우
• 두번째 집부터 터는 경우 = 마지막 집 선택 X 경우 

현재 도둑질하려는 집의 돈 +  max ( (현재집 -2)집의 돈, (현재집 -1)집의 돈 )

 

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dp[1000000] = { 0, };
int solution(vector<int> money)
{
	vector <long> one;
	vector <long> two;
	int msize = money.size();
	one.resize(msize, money[0]);
	two.resize(msize, money[1]);
	two[0] = 0;
	for (int i = 2; i <= msize - 2; i++)
		one[i] = max(one[i - 2] + money[i], one[i - 1]);

	for (int i = 2; i <= msize - 1; i++)
		two[i] = max(two[i - 2] + money[i], two[i - 1]);

	return max(one[msize - 2], two[msize - 1]);
}

int main()
{
	solution({ 1, 2, 3, 1, 2, 3 });
	return 0;
}

Java

import java.util.*;
public class 프로그래머스Lv4_도둑질_Dp {
	static int solution(int [] money)
	{
		//ArrayList<Integer> one;
		//ArrayList<Integer> two;
		int msize =money.length;
		int [] one  = new int [msize+1];
		int [] two  = new int [msize+1];
		
		one[0] = money[0];
		one[1] = money[0];
		one[2] = money[0];
		
		two[0] = money[1];
		two[1] = money[1];
		two[2] = money[1];
		
		//one.resize(msize, money[0]);
		//two.resize(msize, money[1]);
		//two[0] = 0;
		for (int i = 2; i <= msize - 2; i++)
			one[i] = Math.max(one[i - 2] + money[i], one[i - 1]);

		for (int i = 2; i <= msize - 1; i++)
			two[i] = Math.max(two[i - 2] + money[i], two[i - 1]);

		return Math.max(one[msize - 2], two[msize - 1]);
	}

	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		int [] num= {1,2,3,1,2,3};
		System.out.println(solution(num));
	}

}