9465 (1) 썸네일형 리스트형 [백준] 9465 스티커 (JAVA) 풀이 이 문제는 쉬운 DP문제에 속하는 듯하다. 결국 못풀었지만... 일단 알고리즘의 기본 베이스는 DP를 통해 앞에 있던 수들중 가장큰 수를 구하는 것이다. 밑에 있는 코드에서 쉽게 알수있겠지만 DP의 점화식은 다음과 같다. DP[0][j] = MAX(DP[1][j-1] , DP[1][j-2]) + cost[0][j]이다. 나는 처음 이식을 보고 바로 뒤에(j-2)의 같은 행은 왜 비교를 안하는지 궁금했다. 그러나 잠깐 생각해보니 바로 풀렸다. 왜냐면 같은 행의 두번째 뒤까지 비교해서 구한다면(DP[0][j-2])이는 DP[0][j-2]에서 바로 현재 위치로 온다는 것인데 그렇다면 중간에 더하고 올수있는 대각선을 DP[1][j-1] 그냥 뛰어 넘어 버리기 때문에 이는 문제에서 요구하는 최대값이 될수없다.. 이전 1 다음
