https://www.acmicpc.net/problem/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)
'알고리즘 > BOJ' 카테고리의 다른 글
[Python] 백준 13325번: 이진 트리 (0) | 2021.11.23 |
---|---|
[Python] 백준 2591번: 숫자카드 (0) | 2021.11.22 |
[Python] 백준 12869번: 뮤탈리스크 (0) | 2021.11.19 |
[Python] 백준 1563번: 개근상 (0) | 2021.11.19 |
[Python] 백준 1194번: 달이 차오른다, 가자. (0) | 2021.11.19 |
댓글