반응형
https://www.acmicpc.net/problem/2655
2655번: 가장높은탑쌓기
첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
DP 문제는 문제에 맞는 점화식 설계를 못하면 정말 풀기 힘들다...
처음엔 문제 조건에 맞게 백트래킹 형태로 풀어봤지만 시간 초과가 나왔다.
DP로 문제를 풀어내려면
1. 무게 또는 면접 중심으로 벽돌을 정렬한다.
2. table[i] = index i인 벽돌을 가장 아래에 두었을 때의 최대높이
3. 0 <= j < i인 모든 j에서 table[i] = max(table[i], table[j] + height[i]) if area[i] > area[j] 형태로 정의하고 풀어야 한다.
그리고, 시간 초과가 나왔던 backtracking 방식 풀이.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 가장 큰 정사각형 (Level 2) (0) | 2019.12.26 |
|---|---|
| [Python] 프로그래머스. 구명 보트 (Level 2) (0) | 2019.12.25 |
| [Python] 백준 1495. 기타리스트 (0) | 2019.12.23 |
| [Python] 백준 11053. 가장 긴 증가하는 부분 수열 (LIS) (0) | 2019.12.22 |
| [Python] 프로그래머스. 버스 여행 (Level 4) (0) | 2019.12.21 |