[백준/인프런 | 골드3] 가장높은탑쌓기(LIS 응용 / 다시풀기)

문제

[가장 높은 탑 쌓기(LIS 응용)]

 

밑면이 정사각형인 직육면체 벽돌을 사용하여 탑을 쌓고자 한다. 

탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

 

(조건 1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.

(조건 2) 밑면의 넓이가 같은 벽돌은 없으며, 무게가 같은 벽돌도 없다.

(조건 3) 벽돌들의 높이는 같을 수 있다.

(조건 4) 탑을 쌓을 때, 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌을 놓을 수 없다.

(조건 5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

 

 

*입력 설명

첫 번째 줄에는 입력될 벽돌의 수가 주어진다.

입력으로 주어지는 벽돌의 수는 최대 100개이다.

두 번째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌의 밑면의 넓이, 높이 그리고 무게가 차례대로 주어진다.

단, 벽돌의 밑면 넓이와 높이 그리고 무게는 모두 양의 정수이다.

각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다.

 

*출력 설명

첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.

 

 

문제풀이

import sys
sys.stdin = open("zzzz.txt", "r")

n = int(input())
bricks = []
for i in range(n) : 
    width, height, weight = map(int, input().split())
    bricks.append((width, height, weight))
#bricks[벽돌 번호][] 0 - 밑면 너비, 1 - 벽돌 높이, 2 - 벽돌 무게 

#width로 내림차순 정렬
bricks.sort(reverse=True)
dy = [0] * n
dy[0] = bricks[0][1]        #0번 벽돌의 높이는 초기값으로 저장
result = bricks[0][1]

#i는 현재 블록
for i in range(1, n) :
    max_h = 0
    #j는 현재 i블록의 이전 블록
    for j in range(i-1, -1, -1) :
        #밑에 있는 블록의 무게가 더 무거운지 and dp리스트의 최대 높이 찾기
        if bricks[j][2] > bricks[i][2] and dy[j] > max_h :
            max_h = dy[j]               #최대 높이 저장
    dy[i] = max_h + bricks[i][1]        #최대 높이에 현재 벽돌 높이 누적
    result = max(result, dy[i])         #dp 배열의 현재 구간 중 제일 큰가

print(result)

 

안보고 풀기

import sys
sys.stdin = open("zzzz.txt", "r")

n = int(input())
bricks = []
for i in range(n) : 
    width, height, weight = map(int, input().split())
    bricks.append((width, height, weight))
#bricks[벽돌 번호][] 0 - 밑면 너비, 1 - 벽돌 높이, 2 - 벽돌 무게 

#width로 내림차순 정렬
bricks.sort(reverse=True)
dy = [0] * n
dy[0] = bricks[0][1]        #0번 벽돌의 높이는 초기값으로 저장
result = bricks[0][1]

#dy[i]를 구해라 -> dy[i]는 앞에 있는 블록보다 무게가 가벼워야한다
#가벼운 경우 최대 높이 위에 올릴 수 있다 
for i in range(1, n) :      #0은 이미 기본 값, 1~n 까지
    max_h = 0
    for j in range(i-1, -1, -1) :       #i앞까지 본다
        #현재 값 i보다 앞에 있는 블록이 더 무게가 더 큰지 확인([j][2])
        #i보다 j가 무게가 더 큰 경우, 쌓을 수 았음 -> dp 배열에 있는 최대 무게에 누적
        if bricks[j][2] > bricks[i][2] and dy[j] > max_h :
            max_h = dy[j]
        dy[i] = max_h + bricks[i][1]      #높이(1) 누적
        result = max(result, dy[i])       #최대 값 계속 저장(정답 도출용)

print(result)

 

---

https://www.acmicpc.net/problem/2655

2655번: 가장높은탑쌓기

문제

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

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 복사

3
5
3
1

 

값은 같은데 왜 틀릴까 집중해서 다시 보자

import sys
sys.stdin = open("zzzz.txt", "r")

n = int(input())
bricks = []
for i in range(n) : 
    width, height, weight = map(int, input().split())
    bricks.append((width, height, weight))
#bricks[벽돌 번호][] 0 - 밑면 너비, 1 - 벽돌 높이, 2 - 벽돌 무게 

#width로 내림차순 정렬
bricks.sort(reverse=True)
dy = [0] * n
dy[0] = bricks[0][1]        #0번 벽돌의 높이는 초기값으로 저장
result = bricks[0][1]

#dy[i]를 구해라 -> dy[i]는 앞에 있는 블록보다 무게가 가벼워야한다
#가벼운 경우 최대 높이 위에 올릴 수 있다 
for i in range(n) :      #0은 이미 기본 값, 1~n 까지
    max_h = 0
    for j in range(i-1, -1, -1) :       #i앞까지 본다
        #현재 값 i보다 앞에 있는 블록이 더 무게가 더 큰지 확인([j][2])
        #i보다 j가 무게가 더 큰 경우, 쌓을 수 았음 -> dp 배열에 있는 최대 무게에 누적
        if bricks[j][2] > bricks[i][2] and dy[j] > max_h :
            max_h = dy[j]
        dy[i] = max_h + bricks[i][1]      #높이(1) 누적
        result = max(result, dy[i])       #최대 값 계속 저장(정답 도출용)
print(result)

# #최대값 역추적 - 인덱스 구하기
# max_value = result
# idx = n-1 
# submit = []

# while idx >= 0 :
#     if max_value == dy[idx] :         #최대값의 인덱스 찾기
#         submit.append(idx)
#         max_value -= bricks[idx][1]
#     idx -= 1
# #정답 출력
# print(len(submit))
# for s in submit :
#     print(s+1)