[Python] 백준 2643번: 색종이 올려 놓기

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

2643번: 색종이 올려 놓기

• 조건 1 : 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다. 즉, 맨 위의 색종이 밖으로 나가지 않아야 한다.
• 조건 2 : 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다.(색종이를 90˚돌려 놓을 수 있다.)

1. 색종이는 90도 돌릴 수 있으므로 두변중 큰변의 길이를 기준으로 역으로 정렬하면 나머지 한변만 비교하면 된다.

2. dp[i][0] 은 최대로 쌓을수 있는 색종이수, dp[i][1]은 마지막으로 쌓인 길이이다.

3. 현재 쌓으려는 길이가 이전의 dp[i][1]보다 같거나 작아야하고 dp[j][0] + 1 > dp[i][0]이여야 한다. (전의 색종이 길이보다 지금의 색종이의 길이가 더 작으므로 같으면 점화식이 성립하지 않음)

n = int(input())
p = [(1000, 1000)]
ans = 0
for _ in range(n):
    w, h = map(int, input().split())
    p.append((max(w, h), min(w, h)))

p.sort(reverse=True)

dp = [[0, p[i][1]] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(i-1, -1, -1):
        if dp[j][1] >= p[i][1] and dp[j][0] + 1 > dp[i][0]:
            dp[i][0] = dp[j][0] + 1
            dp[i][1] = p[i][1]
            ans = max(ans, dp[i][0])

print(ans)