[BOJ] 1932번: 숫자삼각형

1932번 문제 풀기!

1932번: 숫자삼각형

정말 고민을 많이 했는데 생각보다 간단했었따... 

이게 왜 DP인지 궁금하신 분들을 위해 설명을 하자면 문제 자체가 위층에서 다음을 위해 적절한 녀석을 골라서 현재 층에서 가장 적절한 녀석을 골라 더해주는 것이다. 좀 깔끔하게 설명하지 못해서 그렇긴 한데 재귀적인 성격이 나오는 문제이다.

문제를 보면 ↘, ↙으로 갈 수 있다고 했다. 이건 위에서 아래로 내려갈 때 가정(1)이고, 아래에서 위로 간다고 가정하면 ↖, ↗으로 갈 수 있다.(2)

개인적으로 이런 문제들은 바텀-업 방식을 사용하는 것을 선호하기 때문에 (2)의 가정이 점화식을 세우기에 좋았다.

	[1]	[2]	[3]	[4]	[5]
[1]	7
[2]	3	8
[3]	8	1	0
[4]	2	7	4	4
[5]	4	5	2	6	5

점화식은 dp[i][j] = dp[i - 1][j] 또는 dp[i][j] = dp[i - 1][j - 1]이다.

근데 우리는 max값을 구해야 하므로 점화식 처리한 후에 dp[i][j] 값을 max와 비교해서 최대값 갱신을 해주면 된다.

코드