프로그래머스 - 정수 삼각형

내가 풀어본 문제(못 풀고 다른분들의 풀이를 보고 개념을 이해해서 다음 문제를 기약하기로했따.)는 프로그래머스의 43105번 문제이다.

코딩테스트 연습 > 동적계획법(Dynamic Programming) > 정수 삼각형 url : programmers.co.kr/learn/courses/30/lessons/43105

 

 

 

int solution(vector<vector<int>> triangle) 
{
	int answer = 0;

	//! 아래 노드의 2개의 값과 더해줘야 하기 때문에 하단 결과 입력 메모리를 2배로 만들어줌
	vector<vector<int>> dp(triangle.size());
	for (size_t i = 0; i < triangle.size(); i++)
	{
		//! 처음꺼도 계산해야하므로 처음껀 1개만 입력!
		if(i == 0)
			dp[i].resize(1);
		else
			dp[i].resize((triangle[i - 1].size()) * 2);
	}

	dp[0][0] = triangle[0][0];
	
	for (int i = 0; i < triangle.size() - 1; i++) 
	{
		for (int j = 0; j < triangle[i].size(); j++) 
		{
			int nIdx = j * 2;
			//! 다음 영역 메모리에 값을 더해줌
			dp[i + 1][nIdx] = dp[i][j] + triangle[i + 1][j];
			dp[i + 1][nIdx + 1] = dp[i][j] + triangle[i + 1][j + 1];
		}
	}

	
	answer = *max_element(dp[dp.size() - 1].begin(), dp[dp.size() - 1].end());

	return answer;
}

 

다른 사람들의 풀이를 보고 이해한 다음에 내 나름대로 코드를 짜보았는데... 결과는 좋지 않았다...

 

개념은 이해하고 다른 동적 계획법을 풀기 위해 넘어가기로 했다.