2655번 가장높은탑쌓기
문제
밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.
- 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
- 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
- 벽돌들의 높이는 같을 수도 있다.
- 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
- 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
입력
첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.
출력
탑을 쌓을 때 사용된 벽돌의 수를 빈칸없이 출력하고, 두 번째 줄부터는 탑의 가장 위 벽돌부터 가장 아래 벽돌까지 차례로 한 줄에 하나씩 벽돌 번호를 빈칸없이 출력한다.
예제 입력 1 복사
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2
예제 출력 1 복사
3
5
3
1
n = int(input()) # n = 벽돌의수
array = [] # 벽돌의 번호, 넓이, 높이 , 무게가 들어갈 곳입니다.
array.append([0,0,0,0]) # array를 0으로 초기화 켜줍니다.
for i in range(1, n+1):
area, height, weight = map(int, input( ).split( ))
array.append([i, area, height, weight])# array를 탑처럼 쌓아서 표를 만들어 주는 작업입니다. ##[[0,0,0,0], [1,25,3,4],[2,4,4,6],[3,9,2,3],[4,16,2,5],[5,1,5,2]] 예시를 넣으면 다음과 같이나온다. , 가독성 쉽게 다음과 같이 표로 나타내자.
| 벽돌의 번호 | 넓이 | 높이 | 무게 |
| 0 | 0 | 0 | 0 |
| 1 | 25 | 3 | 4 |
| 2 | 4 | 4 | 6 |
| 3 | 9 | 2 | 3 |
| 4 | 16 | 2 | 5 |
| 5 | 1 | 5 | 2 |
<array>
array.sort(key = lambda data: data[3]) # python의 key값을 이용해서 무게를 기준으로 정렬을 해줍니다!
| 벽돌의 번호 | 넓이 | 높이 | 무게 |
| 0 | 0 | 0 | 0 |
| 5 | 1 | 5 | 2 |
| 3 | 9 | 2 | 3 |
| 1 | 25 | 3 | 4 |
| 4 | 16 | 2 | 5 |
| 2 | 4 | 4 | 6 |
<array.sort>
table = [0] * (n+1) # array에서도 첫번째 행을 0으로 초기화할 값을 넣어줬으니 table에서도 초기화할 행이필요해요!
| 0 | 1 | 2 | 3 | 4 | 5 |
<위 list는 table의 index번호, 직접 만드는 list가 아닌 table의 가독성을 향상시키기위한 참고 list>
| 0 | 0 | 0 | 0 | 0 | 0 |
<table>
for i in range(1, n+1):
for j in range(0, i): # 큰 for문 속 i 가 작은 속 i에 들어간다! 하나하나 비교해보는 알고리즘에서 사용
if array[i][1] > array[j][1]: # array의 넓이가 i 번째 보다 j번째가 더 크다면! 즉 <넓이비교>
table[i] = max(table[i], table[j] + array[i][2]) # table[i]와 table[j] + array[i]의높이를 더한것중 큰것을 table[i]에 넣어 즉 table[i]에는 최대 높이 값이 들어간다.
# i = 1일떄 j = 0 if array[1][1] > array[0][1] 이므로 1 >0 따라서 만족 table[i] = 5가 된다.
| 벽돌의 번호 | 넓이 | 높이 | 무게 |
| 0 | 0 | 0 | 0 |
| 5 | 1 | 5 | 2 |
| 3 | 9 | 2 | 3 |
| 1 | 25 | 3 | 4 |
| 4 | 16 | 2 | 5 |
| 2 | 4 | 4 | 6 |
<array.sort>
| 0 | 5 | 0 | 0 | 0 | 0 |
<table>
#i = 2 일때 j =1일떄 array[2][1] > array[1][1] 9> 1 이므로 만족 따라서 table[i] = 0 과 5+2 중에 큰것을 골라 따라서 7이 들어간다.
| 0 | 5 | 7 | 0 | 0 | 0 |
<table>
# i= 3 일떄 j = 0 이라면 if array[3][1] > array[0][1] 25>0 이므로 만족 따라서 table[i] = 0 , 0+3 3이 들어간다
| 0 | 5 | 7 | 3 | 0 | 0 |
<table>
# i= 3 일떄 j = 1 이라면 if array[3][1] > array[0][1] 25>0 이므로 만족 따라서 table[i] =max(3 , 8)이 들어간다
## 참고
table[j] + array[i][2] == table[1] + array[3][2] , 5 +3 = 8
max(table[i], table[j] + array[i][2])에서 table[i] =3 , table[j] + array[i][2] = 8 따라서 큰 8로 대체된다
| 0 | 5 | 7 | 8 | 0 | 0 |
<table>
# i = 3일떄 j =2 이라면 if문 만족 table[i] = max(8 , 10)이 들어가므로 table[i] 값은 10으로 대체된다!
| 0 | 5 | 7 | 10 | 0 | 0 |
<table>
...
###table[i] = max(table[i], table[j] + array[i][2])
i = 4 일때 j =0이라면 if문 성립 , max(table[4], table[0] + array[4][2]) max(0, 2)
| 0 | 5 | 7 | 10 | 2 | 0 |
<table>
###table[i] = max(table[i], table[j] + array[i][2])
i =4일때 j =1 이라면 if 문성립 ,max(table[4], table[1] + array[4][2]) max(2, 5+2)
| 0 | 5 | 7 | 10 | 7 | 0 |
<table>
###table[i] = max(table[i], table[j] + array[i][2])
i= 4일때 j = 2 이라면 array[4][1] > array[2][1] 16> 9 이므로 if문 성립 max(table[4], table[2] + array[4][2]) 9 와 table
| 0 | 5 | 7 | 10 | 9 | 0 |
<table>
i = 4일때 j = 3 이라면 array[4][1] > array[3][1]: 16 > 25 이므로 if문 성립 안함
| 0 | 5 | 7 | 10 | 9 | 0 |
<table>
..
for문 완료시
| 0 | 5 | 7 | 10 | 9 | 9 |
<table>
max_value = max(table) ## max_value 에는 10이 들어가 있다.
index = n # n = 5라고 문제에 있으므로 index = 0 ,1 ,2 ,3 ,4 ,5 ## 인덱스를 이용한 table의 값찾기
result = []
while index != 0: # 반복문 0이 안될떄까지 반복해
if max_value == table[index]: # index = 3이면 table[index] == max_value 는 10 == 10 즉 참이므로
result.append(array[index][0]) # array[3][0]값 즉 1을 넣어라
| 벽돌의 번호 | 넓이 | 높이 | 무게 |
| 0 | 0 | 0 | 0 |
| 5 | 1 | 5 | 2 |
| 3 | 9 | 2 | 3 |
| 1 | 25 | 3 | 4 |
| 4 | 16 | 2 | 5 |
| 2 | 4 | 4 | 6 |
max_value -= array[index][2] # 10에서 -3을 빼자 = >7이남는다.
즉! max_value = 10이라는것은 최대 높이가 10이라는의미.
10을만든것은 3 +2 + 5 이며 1번벽돌 3번벽돌 5번 벽돌로 이루어진 층이다.
따라서 가장 아래에 위치하고 있는 1번 벽돌부터 빼면서 그 변독의 번호를 부르게 하는 작업이다.
| 5번 넓이1 |
| 3번 넓이 9 |
| 1번 넓이 25 |
index -= 1 # 인덱스를 하나빼준다.
result.reverse() # (1,3,5) => (5,3,1)로 만들어주는 python의 함수
print(len(result))
[print(i) for i in result]
<최종 코드>
n = int(input())
array = []
array.append([0,0,0,0])
for i in range(1, n+1):
area, height, weight = map(int, input().split())
array.append([i, area, height, weight])
array.sort(key = lambda data: data[3])
table = [0] * (n+1)
for i in range(1, n+1):
for j in range(0, i):
if array[i][1] > array[j][1]:
table[i] = max(table[i], table[j] + array[i][2])
max_value = max(table)
index = n
result = []
while index != 0:
if max_value == table[index]:
result.append(array[index][0])
max_value -= array[index][2]
index -= 1
result.reverse()
print(len(result))
[print(i) for i in result]
#본 코드는 패스트캠퍼스 알고리즘/기술면접 완전 정복 올인원 패키지 동적 프로그래밍(나동빈 강사)의 코드를분석한 글입니다.#