그리디알고리즘(2xN 예쁜 타일링/S2)

1. 문제

2021년, 정보대 화장실에서 물이 자꾸 범람하는 탓에 바닥 타일링을 다시 할 지경에 이르렀다. 타일링의 장인 민규는 "언제나 타일링은 예쁘게"라는 좌우명으로 살아왔다. 새로 타일링을 해야 하는 화장실 바닥은 2×N 크기의 격자로 표현이 된다. 민규에게는 2×1 크기의 타일 A개와 2×2 크기의 타일 B개가 있다. 각 타일들에는 "예쁨"의 정도가 있는데, 화장실 바닥의 예쁨은 바닥을 구성하는 타일들의 예쁨의 합이 된다. 민규는 가지고 있는 타일들을 이용해서 화장실 바닥의 예쁨이 최대로 되게 타일링 하려고 한다. 이때, 얻을 수 있는 예쁨의 최댓값은 얼마일까?

예제 1의 예쁨의 최댓값으로 가능한 경우이다. 타일은 90도 회전이 가능하다.

 

2. 입력

첫째 줄에 정수 N, A, B(1 ≤ N, A, B ≤ 2000, 2 × B + A ≥ N)가 공백으로 구분되어 주어진다.

둘째 줄에 각 2×1 크기 타일의 예쁨을 의미하는 정수 A개가 공백으로 구분되어 주어진다.

셋째 줄에 각 2×2 크기 타일의 예쁨을 의미하는 정수 B개가 공백으로 구분되어 주어진다.

각 타일의 예쁨은 1,000,000 이하의 양의 정수이다.

 

5 4 3
1 2 3 4
4 5 6

 

3. 출력

민규가 가지고 있는 타일들을 이용해서 얻을 수 있는 화장실 바닥의 예쁨의 최댓값을 출력하시오.

15

 

4. 코드

import sys

n,a,b = map(int, sys.stdin.readline().split())
aList =list(map(int,sys.stdin.readline().strip().split()))
bList =list(map(int,sys.stdin.readline().strip().split()))
# 타일 예쁨정도 오름차순으로 정렬
aList.sort(reverse=True)
bList.sort(reverse=True)
result = 0

# 타일이 홀수 이면 2*1 타일이 무조건 한개 사용됨
if n%2 == 1:
  result += aList[0]
  del aList[0]

# 화장식 바닥크기(홀수면 -1) 만큼 반복문 수행
for _ in range(n//2):
  aValue = 0
  bValue = 0
  # 리스트 존재여부
  if len(aList) > 1:
    aValue = aList[0] + aList[1]
  if len(bList) > 0:
    bValue = bList[0]
  # 2*1 2개와 2*2 1개의 예쁨정도를 비교하여 결과값 출력
  if bValue < aValue:
    result += aValue
    del aList[0], aList[0]
  else:
    result += bValue
    del bList[0]
    
print(result)

 

5. 풀이 설명

① 2*1타일, 2*2타일을 예쁨정도 오름차순으로 정렬한다.

② 입력받은 바닥의 길이가 홀수 일경우 2*1타일중 가장 큰수를 결과값에 추가한다.

③ ② 에서 홀수일경우를 처리했기에 바닥의길이를 2로 나누어 반복문을 처리한다. 

④ 2*1 타일 2개와 2*2 타일 1개의 예쁨정도를 비교하여 큰수를 결과값에 추가한다.

⑤ 추가한 타일은 리스트에서 제거한다.

 

6. 느낀점

큰 막힘없이 풀었다.