개발자는 눈 아프다

정올 Q1539 가장 높은 탑 쌓기

▶ 문제 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=811&sca=305

가장 일반적인 형태의 다이나믹 프로그래밍 문제이다. 다이나믹 문제에서 유명한 knab과 유사한 형태를 띠고 있다.

조건

1. 넓이, 높이, 무게가 존재하며 동일 높이는 존재하나 동일 넓이, 무게는 없다.

2. 벽돌 위에 쌓으려면 넓이, 무게가 작아야 가능하다.

3. 가능한 모든 경우의 수중 최대 탑 높이를 구하여라

입력값

▶ 문제 접근

 최초 문제 접근 시 다이나믹 형태의 점화 식을 생각하지 못하였다. 그래서 각 벽돌과 그 벽돌 위에 쌓을 수 있는 벽돌을 찾아 2차원 int map을 만드는 형태로 코딩하였다. 답을 구할 수는 있었으나 다이나믹 문제 풀이의 의미가 없으므로 새로 접근해 보았다.

위에 올라갈 수 있는 벽돌의 수를 찾고 그 중 가장 높이가 높은 것과 자기 높이를 해서 자기의 값을 저장한다. 

▶ 문제 풀이

 1. 벽돌을 무게나 넓이에 의해 정렬한다.

위 입력 예시를 넓이에 의해 정렬해 보겠다.

1 5 2

4 4 6

9 2 3

16 2 5

25 3 4

편의상 위에서 순서대로 1번이라 칭하겠다.

1번벽돌 위에 올라갈 수 있는 벽돌은 존재하지 않는다 따라서 자기 높이만 더한 f(1)=5 이다.

2번 벽돌의 경우 1번 벽돌을 위에 올릴 수 있다. 따라서 최대 높이 f(2) = 9이다.

f(3)=7, f(4)=9, f(5)=10이다.

이중 최대 높이는 f(5)로 135번을 쌓은 것이다. 여기서 주의해야 할 점은 이 인덱스는 정렬한 상태이므로 초기 입력 시 받은 인덱스로 변환해 주어야 한다는 것이다.  생각보다 쉽게 풀리는 것이 다이나믹 문제라 할 수 있다.

다이나믹의 경우 N값이 보통 구하려고 하는 혹은 최대 값이 N인 경우가 대부분이다.