if (n == 1) return max(stiker[0][1], stiker[1][1]);
dp[0][1] = stiker[0][1];
dp[1][1] = stiker[1][1];
for (int i = 2; i <= n; i++) {
dp[0][i] = max(dp[1][i - 2], dp[1][i - 1]) + stiker[0][i];
dp[1][i] = max(dp[0][i - 2], dp[0][i - 1]) + stiker[1][i];
}
return max(dp[0][n], dp[1][n]);
12161542 3년 전
아래와 같이 3가지 경우의 수로 나누어 구현하였습니다.
1)
100 20 40
70 10 60
60이 위치한 자리에는 [100->60 , 70->20->60] 두 가지의 경로가 있으니 두 값의 max를 60에 더해줍니다.
40이 위치한 자리에는 [70->40 , 100->10->40] 두 가지의 경로가 있으니 두 값의 max를 40에 더해줍니다.
최종적으로 마지막 열의 두 행의 값 중 max를 출력합니다.
Answer : 160
2)
100 20
70 10
10으로 오는 경로는 한 가지 뿐이므로 100을 더해줍니다.
20으로 오는 경로도 한 가지 뿐이므로 70을 더해줍니다.
최종적으로 마지막 열의 두 행의 값 중 max를 출력합니다.
Answer : 110
3)
100
70
두 값 중 max를 출력합니다.
Answer : 100
반례나 틀린부분이 있다면 지적 부탁드립니다 !!
p.s)게시판에 존재하는 모든 반례와 TC는 제대로 출력되었습니다