99클럽 코테 스터디 19일차 TIL - 43105 정수 삼각형

43105. 정수 삼각형 / c++ / level3 / 26분

문제 및 코드

접근 방식

동적 계획법

1. 위에서 아래로 내려간다면, 어떤 루트를 결정해야 큰 값이 나올지 모를 수 있지만, 반대로 아래에서 위의 값을 고른다면, 무조건 둘 중 큰 값을 고르기만 하면 된다.
2. 해당 식을 DP라는 함수로 만들어서 저장 (이 때, 인자값으로 row, col 변수를 넘겨주는데, 만약 삼각형의 범위를 넘어간 값이라면 0을 리턴)
3. 맨 아랫줄의 모든 칸에 대해 DP를 수행하면, 순차적으로 위로 타고 올라가며 결국 모든 칸의 계산값이 구해지게 된다.
4. 따라서 맨 아랫줄의 계산 값 중, 가장 큰 값을 고르면 그 값이 나올 수 있는 가장 큰 값이다.

생각해 볼 점

1. 예전에 풀었던 문제라 로직 자체는 쉽게 생각해낼 수 있었는데, 배열로 선언하여 아랫줄에서 윗줄을 검사할 때는 실패가 떴었다. (아마 내가 구현을 잘못하거나, 예외처리를 빠트린게 있었겠지..?)
2. 다시 처음부터 만들 때, DP를 함수로 빼고, dp[row][col]이 계산되어 있지 않다면, 윗줄의 왼쪽 값, 오른쪽 값을 다시 재귀적으로 DP 함수를 호출하도록 구현했더니 통과했다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL