알고리즘/백준(acmicpc.net) 문제풀이
1932번 : 정수 삼각형
Mosu(정종인)
2018. 6. 4. 14:38
반응형
dp로 해결했습니다.
레벨을 i라고 할 때 그 전레벨인 i-1레벨에서 각각의 정수 j (i-1레벨에 대한 j는 총 i-1개만큼 있습니다)에 대한 dp를 해당 칸을 포함한 정수의 합의 최댓값으로 설정합니다. 즉 dp[i][j]는 그 전 레벨의 인접한 두 노드중 더 큰 값을 선택합니다.
여기서 arr[i][j]의 그 전레벨에 인접한 두 노드는 arr[i-1][j-1] 와 arr[i-1][j]입니다. ex)arr[3][2]의 그 전레벨에 인접한 두 노드는 arr[2][1]와 arr[2][2]가 됩니다.
하지만 여기서 한가지 생각해보아야 할 것은 arr[2][2]의 전레벨에 인접한 두 노드는 arr[1][1]과 arr[1][2]가 되어야 하는데 arr[1][2]에는 값이 없습니다. 이것은 초기화를 모두 삼각형에 들어갈 수 있는 범위인 0부터 9999의 최솟값인 0으로 해서 입력을 하면 모두 해결됩니다. arr[3][1]의 인접값도 arr[2][0]과 arr[2][1]이 되지만 arr[2][0]은 이미 0으로 초기화되어있기 때문에 값에는 지장이 없습니다.
따라서 arr[i][j]에 정수 삼각형을 입력받을 때, 식으로 보면 dp[i][j]=MAX(dp[i-1][j-1], dp[i-1][j])+arr[i][j]가 됩니다.
반응형