[백준(BOJ)/C++] 1932번: 정수 삼각형 - 코딩밥상

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

• 접근 방법, 논리 흐름(알고리즘)
  

 우선 점차적으로 내려갈 수 있는 경우의 수를 생각해 보았고, 각 점마다 최댓값을 저장하기에 전 칸을 더하여 저장하는 dp로 풀 수 있다고 생각했다.

문제를 보고 그림을 그려보고 가능한 길을 모두 그려본 결과 다음과 같은 패턴을 발견할 수 있었다.

가장 왼쪽과 가장 오른쪽 즉 삼각형의 변에 해당하는 끝 점들은 올라가는 경우의 수가 바로 위점 하나이다.

반면 끝 점들이 아닌 중간 점들의 경우 왼쪽과 오른쪽으로 올라 가는 경우가 있는데, 최댓값을 구하는 것이니 당연히 두 점 중 더 큰 값으로 올라가는것이 답이 된다.

 

 

• 풀이 코드