728x90
> Dynamic programming(동적계획법)
📖 문제 : 가장 높은 탑 쌓기
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오.
(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 수도 있다.
(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. (조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
입력설명
입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높 이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터연속적 인 번호를 가진다.
출력설명
첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.
입력예제 1
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2
출력예제 1
10
내 코드
if __name__ == "__main__":
n = int(input())
l = []
dy = [0]*n
for i in range(n):
s, h, g = map(int, input().split())
l.append((s, h, g))
l.sort(reverse=True)
dy[0] = l[0][1]
for i in range(1, n):
h_max = 0
for j in range(0, i):
if l[i][2]<l[j][2] and h_max<dy[j]:
h_max = dy[j]
if h_max==0:
dy[i] = l[i][1]
else:
dy[i] = l[i][1] + h_max
print(max(dy))
Point ! ⭐️
- 벽돌을 쌓기 위해서 위에 쌓아올린 벽돌의 넓이와 무게가 아래 벽돌보다 값이 다 작아야 하므로
먼저 밑면의 넓이를 내림차순으로 정렬 후, 무게를 검사한다.
그리고 dy 라는 리스트를 만들고 정의를 하면 dy[2] 는 벽돌 리스트 인덱스 2에 있는 벽돌이 가장 위에 있을 때 쌓아올릴 수 있는 최대 높이 값이 들어간다.
만약 밑면의 넓이가 9이고, 무게가 3인 벽돌이 제일 위에 있을 때, 밑에 둘 벽돌은 (25,3,4) 또는 (16,2,5)인 벽돌이 되는데
(두개를 모두 놓을 순 없음) 이때 두개 중에 더 높이가 높은 벽돌(25,3,4)을 놓아야 최대 높이를 쌓을 수 있다.
결국 dy[2]는 벽돌(25,3,4)의 3 + 자기자신(9,2,3)의 2를 더해 5값이 들어가는 것이다.
즉 높이를 비교하여 최댓값을 넣어줘야 한다는 것 !
- 그리고 위의 내 코드에서는 max(l)을 하여 최댓값을 찾아 넣어주는데 시간 복잡도를 줄이기 위해서는
res라는 정수형 변수에 res = max(a,b) 이런 식으로 for문이 돌아가면서 업데이트를 해줘야할 것 같다.
출처
- 인프런 : 파이썬 알고리즘 문제 풀이
728x90