[파이썬/Python] 백준 18230번: 2xN 예쁜 타일링

📌 문제 : 백준 14247번

---

📌 문제 탐색하기

N : 화장실 가로 크기 $(1 ≤ N ≤ 2000, 2 × B + A ≥ N)$
A : 2×1 크기의 타일 개수 $(1 ≤ A ≤ 2000)$
B : 2×2 크기의 타일 개수 $(1 ≤ B ≤ 2000)$
beauty : 각 타일의 예쁨 $(1 ≤ beauty ≤ 1,000,000)$

화장실 바닥 크기 내에서 2×1, 2×2 크기의 타일을 활용해 타일링했을 때 얻을 수 있는 예쁨의 최댓값을 구하는 문제이다.
화장실 바닥은 항상 세로가 2이고, 타일을 90도 회전할 수 있다.

문제 풀이

0️⃣ 최댓값을 위한 정렬

예쁨의 최댓값을 구해야 하기 때문에 2×1, 2×2 크기의 타일들의 예쁨을 오름차순 정렬한다.

1️⃣ N이 홀수인 경우

N이 홀수인 경우엔 반드시 2×1 크기인 타일이 하나 들어가야만 한다.
따라서 조건에 따라 2×1 중 가장 예쁨이 높은 타일을 먼저 배치한다.

2️⃣ 남은 공간 채우기

가로 길이가 짝수가 된 남은 공간이 다 찰 때까지, 2×1, 2×2 크기의 타일들을 적절히 활용해 채워야 한다.

남은 타일 개수와 남은 공간에 유의하면서 배치한다.

• 2인 타일, 1인 타일 각각만 사용할 수 있는 경우를 따로 고려한다.
• 두 타일 모두 사용 가능할 경우, 1인 타일 2개와 2인 타일 1개 중 예쁨이 더 큰 경우를 우선 배치할 수 있도록 한다.

가능한 시간복잡도

타일 정렬 → $O(A log(A) + B log(B))$
남은 공간 없을 때까지 반복 → $O(N)$

최종 시간복잡도
$O(A log(A) + B log(B))$이다.
최악의 경우 $O(2000 log 2000)$이 되므로 2초 내에 연산 가능하다.

알고리즘 선택

정렬 후 최대 예쁨 값 갖도록 공간 채우기

---

📌 코드 설계하기

1. N, A, B 입력
2. A개 이쁨 저장
3. B개 이쁨 저장
4. 오름차순 정렬
5. 총 예쁨 합 저장할 변수 정의
6. 채워야 할 공간 정의
7. N이 홀수인 경우 고려
8. 남은 공간 채우기
9. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

• 런타임 에러 (IndexError)가 발생했다. 리스트를 pop하는 과정에서 리스트에 값이 하나도 없을 때 그 값을 접근하려고 해서 발생한 에러인 것 같다.
• 조건문에 리스트에 요소가 있는지 확인하는 구문을 추가하여 해결했다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# N, A, B 입력
N, A, B = map(int, input().split())

# A개 이쁨 저장
A_beauty = list(map(int, input().split()))

# B개 이쁨 저장
B_beauty = list(map(int, input().split()))

# 오름차순 정렬
A_beauty.sort()
B_beauty.sort()

# 총 예쁨 합 저장할 변수 정의
beauty_sum = 0

# 채워야할 공간 정의
space = N

if space % 2 == 1:
    if A_beauty:  
        beauty_sum += A_beauty.pop()
        space -= 1

# 남은 공간 없을 때까지 채우기
while space > 0:
    if len(A_beauty) < 2 and len(B_beauty) == 0:
        break  
    
    if len(B_beauty) > 0 and (len(A_beauty) < 2 or B_beauty[-1] > A_beauty[-1] + (A_beauty[-2] if len(A_beauty) > 1 else 0)):
        beauty_sum += B_beauty.pop()
    else:
        if len(A_beauty) >= 2:
            beauty_sum += A_beauty.pop() + A_beauty.pop()
        elif len(A_beauty) == 1:
            beauty_sum += A_beauty.pop()

    space -= 2

# 결과 출력
print(beauty_sum)

• 결과