76.가장 높은 탑 쌓기
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.
(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
(조건3) 벽돌들의 높이는 같을 수도 있다.
(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
▣ 입력설명
입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.
▣ 출력설명
첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.
▣ 입력예제 1
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2
▣ 출력예제 1
10
내 코드
n=int(input())
lst=[list(map(int,input().split())) for _ in range(n)]
# 같은 넓이/무게는 없다고 했으므로 넓이/무게 하나에 대해서만 내림차순 정렬하면 된다. 람다 쓸 필요 없음
lst=sorted(lst, key=lambda x: (x[0],x[2]), reverse=True)
dy=[0]*(n)
dy[0]=lst[0][1]
for i in range(1,n):
max_num=0
for j in range(i-1,-1,-1):
# 이미 넓이/무게 중 하나는 정렬되어 있으므로 정렬하지 않은 조건만 크기비교하면 된다.
if lst[j][0]>lst[i][0] and lst[j][2]>lst[i][2] and dy[j]>max_num:
max_num=dy[j]
dy[i]=max_num+lst[i][1]
print(max(dy))쓸데없는 코드가 많기는 하지만 지금까지의 문제를 응용해 비교 대상을 추가하고 정렬한 후 반복문을 수행했다.
풀이
n=int(input())
bricks=[]
for i in range(n):
a, b, c=map(int, input().split())
bricks.append((a, b, c))
bricks.sort(reverse=True)
dy=[0]*n
dy[0]=bricks[0][1]
res=bricks[0][1];
for i in range(1, n):
max_h=0;
for j in range(i-1, -1, -1):
if bricks[j][2]>bricks[i][2] and dy[j]>max_h:
max_h=dy[j]
dy[i]=max_h+bricks[i][1]
res=max(res, dy[i])
print(res)지금까지 풀었던 최대 부분 증가 수열을 약간 응용한 문제이다. 지금까지의 문제와 다른 점은 크기를 비교할 대상이 추가된 점, 정렬을 할 수 있게 된 점이다.
반성점
- 문제를 제대로 읽지 않아 불필요한 코드가 많았다.
배운 것
