몇번 풀었냐?

• 21년 10월 4일 월요일

풀이전략

• 문제를 보면 대각선 왼쪽, 오른쪽 아래로 향하면서 가장 큰값을 출력해는 문제이다.

• 처음 생각으로는 아래를 보았을때 가장 큰 친구를 뽑아서 진행할까?
  라는 생각을 했지만,,,, 추후를 생각했을때 문제가 될 소지가 있는 생각이다.
  왜냐하면 8을 선택했다면... 7-3-8 이 합이 7-8-1 보다 값이 클것이다 라는 것을 파악할 수 있다.
  
  -> 아래 중 가장 큰 친구를 선택해서 하는 방법은 잘못되었다 라는 것을 생각할 수 있다. 다른 방법을 생각해보자.

• 7-3 /// 7-8 을 모두 계산하고
  밑으로 향해서도 7-3-8 // 7-3-1 ?? 7-8-1 // 7-8-0
  이렇게 생각할 수 있따.

• 한번 더 해보자.
  7-3-8-2 // 7-3-8-7 ?? 7-3-1-7??? //7-3-1-4??? 7-8-1-4 // 7-8-0-4
  => 느낀 점. 가운데 있는 친구는 상단 우측과 상단 좌측의 값을 비교해서 가장 큰 친구를 선택해서 가산을 진행해야 한다는 것을 캐치 할 수 있다.

수도 코드
일단 반복문 2개를 써야 겠다!
for(int i = 0; i < size();
{
for(int j = 0; j < [i].size();)
{
//[1][0] = [0][0];
//[1][1] = [0][0];
//[2][0] = [1][0];
//[2][2] = [1][1];
//[2][1] = [1][0] vs [1][1]
이런식이다.
그림 참고하면 됨

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    for(int i = 1; i < triangle.size(); i++)
    {
        for(int j = 0; j < triangle[i].size(); j++)
        {
            //맨 처음값.
            if(j == 0)
            {
                triangle[i][j] += triangle[i - 1][j];
            }
            //맨 마지막 값.
            else if(j == triangle[i].size() - 1)
            {
                triangle[i][j] += triangle[i - 1][j -1];
            }
            //사이값
            else
            {
                int upLeft = triangle[i][j] + triangle[i - 1][j -1];
                int upRight = triangle[i][j] + triangle[i -1][j];
                
                if(upLeft > upRight)
                {
                    triangle[i][j] = upLeft;
                }
                else
                {
                    triangle[i][j] = upRight;                  
                }               
            }            
        }
    }
    
    int highIndex = triangle.size() -1 ;
    answer = triangle[highIndex][0];
      
    for(int i = 0; i < highIndex; i++)
    {
        answer =  max(answer, triangle[highIndex][i]);
    }
    
    return answer;
}