고층 빌딩

[백준 1328] 고층 빌딩 C++

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일반적인 dp문제는 작은 부분 문제들을 해결하면서 큰 문제의 답을 찾는 느낌인데 이 문제는 조금 다른 느낌이다. (도저히 안 풀려서 힌트를 얻었다) 일단 dp배열은 dp[최대 높이][왼쪽에서 보이는 건물 수][오른쪽에서 보이는 건물 수] 이렇게 설정했다. dp배열을 정해주는 건 어렵지 않았다. 그리고 bottom up 방식으로 푸는 게 좋을 것 같다는 느낌이 크게 들었었다. 그런데 점화식을 도출하기가 정말 어려웠다. ..