• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

정렬이 아닌 넓이, 무게를 비교하여 풀수는 없을까요?

20.12.30 20:44 작성 조회수 99

0

선생님 안녕하세요.

강의를 통해 많이 배우고 있습니다.

좋은 강의 감사합니다.

혹시 정렬을 통해 비교조건을 1개만 남기는게 아닌

넓이, 무게를 모두 사용하여 풀수는 없을까요?

넓이, 무게를 모두 사용해서 풀려고하니

5
14 5 18
12 10 9
13 12 12 # 오류 원인 케이스 5+12+10 으로 블록쌓기 불가
5 6 19
8 13 7

위와 같은 케이스에서

최대값 : 5+12+10+13 = 40 이 아닌

5+12+7 = 30 으로 오류가 발생합니다..

(그동안 쌓은 블록 중간에 다른 블록을 넣는것에 실패)

혹시 몰라 코드도 첨부드리지만

풀이까지는 무리한 질문 같아, 

넓이 무게를 모두사용해서 풀 수 있는 방법 조언 주시면 감사하겠습니다.

import sys
sys.stdin=open("input.txt", "r")
    
if __name__=="__main__":
    N = int(input())
    b = []
    for _ in range(N):
        b.append(tuple(map(int, input().split())))
    dy = [0]*N

    for idx in range(N):
        max_h = b[idx][1]
        # v (area, height, weight)
        for i, v in enumerate(b[:idx]):
            # 넓이, 무게 조건 체크
            if v[0] > b[idx][0] and v[2] > b[idx][2]:
                if (dy[i] + b[idx][1]) > max_h:
                    max_h = dy[i] + b[idx][1]
        dy[idx] = max_h
print(max(dy))

답변 2

·

답변을 작성해보세요.

2

안녕하세요^^

넓이나 무게 중 하나는 정렬하고 다이나믹히야 합니다. 정렬하지 않고 둘다 체크하면서 푸는 것은 저도 모르겠습니다.

0

mentha님의 프로필

mentha

질문자

2021.01.02

선생님 감사합니다 ^^

새해 건강하시고 복 많이 받으세요!