정수 삼각형 (c++)

1. 문제

코딩테스트 연습 - 정수 삼각형 | Programmers School

프로그래머스

2. 풀이

누적합을 푸는 방식처럼 생각. 전부 더한 값을 저장하고, 그 값을 사용해서 triangle[i][j] 값을 구함

 

1. triangle[0][0] 부터 삼각형의 높이만큼 더한 값을 차례대로 저장

• 가장자리의 [i][0]부분과 [i][i]부분은 그냥 더함
• 내부 삼각형은 [i - 1][j - 1]이랑 더한 값과 [i - 1][j]랑 더한 값을 비교해서 더 큰 값을 저장

2. 삼각형 밑부분을 확인해서 가장 큰 값을 반환

3. 생각

• 처음에는 재귀의 방식으로 풀어볼까 생각했지만, 시간이 너무 오래걸렸음 → 동적계획법으로해결

 

shin0112/programmers_cpp: programmers' coding test solutions (github.com)

출처 : 프로그래머스 코딩 테스트 연습 - 정수 삼각형
https://school.programmers.co.kr/learn/courses/30/lessons/43105