[python] 백준 2643 색종이 올려 놓기

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

2643번: 색종이 올려 놓기

 

 

문제 해결

• 작은 것부터 쌓아 올려서 최대한 많이 쌓을 수 있도록 하면 된다.
• w, h가 구별되지 않으므로 두 변중 긴 변을 w, 작은 변을 h로 정렬한다.
• 각 색종이를 길이가 큰 것 부터 내림차순으로 정렬한다
• 하나씩 확인하면서 이전 것들 길이를 비교하면서 w, h 모두 더 길 때 dp[w][h] (가장 큰 색종이의 길이가 w, h일 때 쌓아올릴 수 있는 최대 개수) 를 dp[pw][ph]+1 (이전 것들을 이용해서 더 쌓아 올릴 수 있는 개수)과 dp[w][h] (현재 쌓아 올릴 수 있는 개수)를 비교해서 dp[w][h]를 수정한다.
•  

CODE

import sys
input = sys.stdin.readline


def main():
    if len(L) == 0:
        print(0)
        return

    dp = [[0 for _ in range(1001)] for _ in range(1001)]
    stack = [(0,0)]
    while len(L):
        w, h = L.pop()
        dp[w][h] = 1
        for i in range(len(stack)-1,-1,-1):
            pw, ph = stack[i]
            if pw <= w and ph <= h:
                dp[w][h] = max(dp[pw][ph] + 1, dp[w][h])
                # if dp[w][h] == dp[pw][ph]+1:
                #     print(f'{w}, {h} = {dp[w][h]}')
        stack.append((w, h))
    ans = 0
    for w, h in stack:
        ans = max(ans, dp[w][h])
    print(ans)
    return


if __name__ == "__main__":
    n = int(input())
    L = []
    for _ in range(n):
        l = sorted(list(map(int, input().split())), reverse=True)
        L.append(l)
    L = sorted(L, key = lambda x: (x[0],x[1]), reverse=True)
    main()