정수 삼각형1 [Swift][DP] 백준 1932번 (정수삼각형) 요구능력 : DP에 대한 이해 코드설명 : 문제를 읽고 우선적으로 생각해볼 수 있는건 dp[i]를 구하려면 이전에 어떤 값을 골랐는지가 중요하다는것이다. 삼각형에서 한줄을 i줄이라고 한다면 몇번째 수를 선택했는지가 중요한것이다. 이것을 보고 dp는 2차원 배열로 이루어지겠구나를 생각했다. 조건은 왼쪽대각선 혹은 오른쪽대각선으로만 선택할 수 있는것이다. 문제의 예제를 보고 8, 1, 0이 있는 줄을 dp[i]라고 생각해보면 이전 줄에 3, 8이 있다. 우선 8을 선택했을 때의 최대값을 구하기 위해서는 3에서 내려오는 방법밖에는 없다. 왼쪽 대각선으로 내려오는 것 밖에 없는것이다. 다음으로 1을 생각해보자. dp[i][1]을 구하는것인데 1은 왼쪽대각선과 오른쪽대각선 2가지가 모두에서 내려올 수 있다. 다.. 2021. 11. 9. 이전 1 다음