[백준/2643] 색종이 올려 넣기 (Python)

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

2643번: 색종이 올려 놓기

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:20:48

 

---

 

문제 설명

 

크기가 모두 다른 직사각형 모양의 색종이가 여러 장 있다. 색종이를 하나씩 올려 놓아, 되도록 많은 장수의 색종이들을 쌓으려고 한다.

새로 한 장의 색종이를 올려 놓을 때는 지금까지 쌓아 놓은 색종이들 중 맨 위의 색종이 위에 올려놓아야 하며 아래의 두 조건을 모두 만족해야 한다.

조건 1 : 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야 한다. 즉, 맨 위의 색종이 밖으로 나가지 않아야 한다.
조건 2 : 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다.(색종이를 90˚돌려 놓을 수 있다.)
예를 들어, 아래의 그림 중에서 위의 두 조건을 모두 만족하는 경우는 (나)뿐이다.

색종이는 두 변의 길이로 표현된다. (3, 5)는 두 변의 길이가 각각 3과 5인 색종이를 나타낸다. 예를 들어, 다음과 같이 7장의 색종이가 주어졌다고 하자 : (1, 2), (8, 7), (20, 10), (20, 20), (15, 12), (12, 14), (11, 12) 위의 조건을 만족하면서 가장 많이 쌓을 수 있는 색종이들의 순서는 (20, 20), (15, 12), (12, 14), (11, 12), (8, 7), (1, 2)이다.

입력으로 색종이들이 주어졌을 때, 위의 조건 1과 조건 2를 만족하면서 쌓을 수 있는 최대 색종이 장수를 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 작은 자연수이다.

 

출력

쌓을 수 있는 최대 색종이 장수를 출력한다.

 

입력 예시

7
1 2
8 7
20 10
20 20
15 12
12 14
11 12

 

출력 예시

6

 

 

---

 

풀이

 

DP[i]를 i번째 색종이가 제일 위에 있을 때의, 최대 색종이를 쌓은 경우의 수라고 가정하자. i보다 인덱스가 큰(더 뒤에 있는), DP[j]에 대해서 다시 생각해 보자. j번째 색종이가 i번째 색종이 위에 올라갈 수 있다면 다음 수식이 성립한다 :

 

DP[i] = max(DP[j], DP[i] + 1)

 

또한, 이를 정렬하기 위해선 넓이 순으로 정렬하는 전제조건이 필요하다. 넓이가 같은 두 사각형은 합동인 사각형을 제외하고 겹칠 수 없다. DP를 모두 업데이트하고 그 중 최댓값을 출력하면 된다.

 

• init : 초기화함수. paper_list를 입력받고 이를 넓이 순으로 정렬하여 반환한다.
• make_dp : 인자로 받은 paper_list를 통하여 dp를 작성하고 그 중 최댓값을 출력한다.
• solve : 메인함수. init으로 전달받은 paper_list를 make_dp를 호출하여 삽입한다.

 

풀이 코드

 

N = int(input())

def init() :
  paper_list = [list(map(int, input().split())) for _ in range(N)]
  paper_list.sort(key = lambda x : -x[0]*x[1])
  return paper_list

def make_dp(paper_list) :
  dp = [1]*N

  for i in range(N-1) :
    ih, iw = paper_list[i]
    for j in range(i+1, N) :
      jh, jw = paper_list[j]
      if ih >= jh and iw >= jw or ih >= jw and iw >= jh :
        dp[j] = max(dp[j], dp[i] + 1)

  print(max(dp))
  
def solve() :
  paper_list = init()
  make_dp(paper_list)

solve()

풀이완료~