.PNG)
75. 가장 높은 탑 쌓기
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래
에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프
로그램을 작성하시오.
(조건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
출처 : 한국정보올림피아드
<내 풀이>
잘 풀었다고 생각했는데 예제 1에서만 정답이었음
=>
19 10 5 / 7 12 14 /8 13 7 => 이런 경우에서 안된다
ar=[0]
h=[0]
w=[0]
n=int(input())
for i in range(n) :
a,b,c=map(int,input().split())
ar.append(a)
h.append(b)
w.append(c)
dy=[0]*(n+1)
dy[1]=min(h)
for i in range(1,n+1) :
s=0
for j in range(1,n+1):
if ar[i]>ar[j] and w[i]>w[j] :
s+=h[j]
dy[i]=h[i]+s
print(dy)
=>풀이 듣고 구현하면서 겪은 시행착오
max 를 dy중에서 갱신해줘야 하는데 h에서 갱신했음
ar=[0]
h=[0]
w=[0]
n=int(input())
k=[]
for i in range(n) :
(a,b,c)=map(int,input().split())
k.append((a,b,c))
k.sort(reverse=True)
for i in range(len(k)) :
ar.append(k[i][0])
h.append(k[i][1])
w.append(k[i][2])
dy=[0]*(n+1)
dy[1]=h[1]
for i in range(1,n+1) :
maxx=0
s=0
for j in range(i) :
if w[i]<w[j] and dy[j]>maxx : #만약 밑에 여러개의 벽돌이 올 수 있으면 dy중에서 맥스인것으로..
maxx=dy[j]
dy[i]=h[i]+maxx
print(max(dy))
<풀이>
- 처음에 넓이 큰 순으로 정렬해서 넓이, 높이, 무게를 각 넣어주기,
- 그리고 각 벽돌들을 맨 밑에 있을 때로 가정하는 게 아니라 맨 위에 자리하고 있을 때라고 가정하면서 접근해주기
- dy는 자기랑 자기 밑에 올 수 있는 애들 더한 높이
- 그리고 내 앞에 있는 애들은 이미 넓이는 나보다 큰 애들이므로, 무게만
체크해주면 된다. 앞에 있는 애 무게가 나보다 크면 얘는 내 밑에 올 수 있음
따라서 이 아이의 dy[j]+h[i]해주면 됨
if __name__=="__main__":
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)
<반성점>
- 간과한 부분이 아주 많았음.. dy에 누적해준다는 것 잊지 말자
<배운 점>
- 뒤죽박죽이면, 정렬해주고 나서 기준을 하나만 삼고 접근해주기
<2차 내 풀이>
=>예제 4, 예제 5 케이스에서 정답보다 1 적게 나온다. 어떤 부분이 잘못된 것일까?
n=int(input())
tot=[]
for i in range(n) :
s,h,w= map(int,input().split())
tot.append((s,h,w))
tot.sort(reverse=True)
tot.insert(0,0)
dy=[0]*(n+1)
dy[1]=tot[1][1]
for i in range(2,n+1) :
maxi=-1
for j in range(1,i):
if tot[j][2]>tot[i][2] and dy[j]>maxi:
maxi=dy[j]
dy[i]=maxi+tot[i][1]
print(max(dy))