[Programmers 코딩테스트 고득점 Kit] 정수 삼각형

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/43105

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

기존에 풀어봤던 유형인 DP 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 삼각형을 좌표로 표현하면 1층은 [0, 0], 2층은 [1, 0], [1, 1], ..., N층은 [N-1, 0], [N-1, 1], ... [N-1, N-1]로 표현할 수 있습니다.

2. 따라서, [0, 0]부터 시작해서 재귀함수로 왼쪽, 오른쪽 중 결과물이 더 큰 쪽으로 움직이도록 코드를 작성해줍니다.

2.1 이 때, 밑으로 내려갈수록 같은 칸을 지나가는 케이스가 많아지므로 [열, 행] 기준으로 DP를 적용해줍니다.

2.2 삼각형이 N층일 때 제일 큰 좌표가 N - 1이므로 N층에 도달하면 기저사례로 0을 반환해주면 됩니다.

3. 2번에서 좌표가 [0, 0]에서 시작했으므로 cache 배열 내 [0, 0]이 거쳐간 숫자의 최댓값을 지니고 있습니다. 따라서, cache[0][0]을 반환해줍니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~