[알고리즘|파이썬] 백준 18230 2xN 예쁜 타일링

문제 링크: https://www.acmicpc.net/problem/18230

 

📌 문제 탐색하기

시간 제한: 2초
메모리 제한: 512 MB

 

✏️ 구해야 하는 정답

문제

2 x N 타일을 채우려고 한다.  2×1 크기의 타일 A개, 2×2 크기의 타일 B개가 있고, 각 타일은 "예쁨"의 정도가 있는데, 가지고 있는 타일들을 이용해서 화장실 바닥의 예쁨이 최대로 되게 타일링 하려고 한다. 이때, 얻을 수 있는 예쁨의 최댓값은 얼마일까?

 

조건

- 1 ≤ N, A, B ≤ 2000

- 2 × B + A ≥ N

- 타일은 90도 회전이 가능

---

📌 풀이하기 

예시

N = 5, A = 4, B = 3

A = {1, 2, 3, 4}

B = {4, 5, 6}

 

그림에서 보이듯, 2x1 2개와 2x2 1개의 예쁨을 비교해서 더 큰쪽을 골라서 채워넣고, 2x1 타일이만 들어가는 경우에는 2x1 타일 중 가장 큰 것을 넣으면 최댓값을 구할 수 있다.

 

---

📌 코드 설계하기

1. N, A, B 값과 a_list, b_list input을 받는다.

2. a_list, b_list를 sort 시켜 큰 값부터 작은 값 순서로 list를 정렬한다.

3. m = 0 으로 예쁨을 담을 변수를 초기화 해준다.

4. while curr < N 동안 loop를 돌게하고, 2x1 2개, 또는 2x2 1개를 선택했을때 curr += 2 를 해주고, 2x1 1개를 선택했을때는 curr += 1을 해준다. 선택한 타일의 예쁨은 m에 더해준다.

4.  N이 짝수인 경우 2x2 1개와 2x1 2개 중 더 예쁜 타일을 선택해주고, N이 홀수인 경우 가장 예쁜 타일 하나를 빼두고 짝수와 동일하게 처리한다.

5. m을 출력한다.

---

📌 시도 회차 수정 사항

1회차: 런타임 에러 (IndexError)

n, a, b = map(int, input().split())
a_list = list(map(int, input().split()))  # 2x1 타일
b_list = list(map(int, input().split()))   # 2x2 타일
m = 0
curr = 0

a_list.sort(reverse=True)
b_list.sort(reverse=True)
i = 0
j = 0

while curr < n:
    if curr == n-1:
        m += a_list[i]
        curr += 1
        i += 1
    elif j > b - 1 or i <= a - 2 and a_list[i] + a_list[i+1] >= b_list[j]:
        m += a_list[i] + a_list[i+1]
        curr += 2
        i += 2
    else:
        m += b_list[j]
        curr += 2
        j += 1
print(m)

i, j 로 리스트 인덱스를 관리해서 문제를 풀었을때 인덱스 에러가 났다.

인덱스 관리가 힘들어서 list에서 필요한 값을 pop 하는 형태로 접근을 바꾸어 풀었다.

---

📌 정답 코드

n, a, b = map(int, input().split())
a_list = sorted(list(map(int, input().split())))
b_list = sorted(list(map(int, input().split())))
m = 0

if n % 2 == 1:
    m += a_list[-1]
    a_list.pop(-1)
    n -= 1

for _ in range(0, n, 2):
    t1, t2 = 0, 0
    if len(a_list) >= 2:
        t1 = a_list[-1] + a_list[-2]
    if len(b_list) >= 1:
        t2 = b_list[-1]

    if t1 > t2:
        m += t1
        a_list.pop()
        a_list.pop()
    else:
        m += t2
        b_list.pop()

print(m)