[백준] 2xN 예쁜 타일링 (18230번)

난이도 : Silver1
Link : https://www.acmicpc.net/problem/18230
Tag : 그리디 알고리즘, 정렬
풀이일자 : 2024년 8월 23일

📌 문제 탐색하기

2 * N : 타일의 크기
A : 2 x 1 타일의 갯수
B : 2 x 2 타일의 갯수
둘째 줄 : A 타일의 예쁨 정도
셋째 줄 : B 타일의 예쁨 정도

가장 이쁜 타일들로 깔아야 함으로 정렬 후 가장 큰것 부터 까는 것이 좋아보이는 문제이다.

가능한 시간복잡도

매번 리스트에서 가장 예쁜 타일을 찾는 것은 시간복잡도상 N x A x B 까지 반복 될 수 있어 문제가 발생 할 수 있으므로 정렬을 통해 찾고 pop을 통해 깔은 타일을 없애고자 한다.

📌 문제 접근 방법

그리디 알고리즘을 통해 가장 예쁜 타일을 까는 것을 찾아보자.
먼저 타일의 크기를 살펴보자
1. 타일의 크기중 변화하는 값인 N 이 짝수일때
2. 타일의 크기중 변화하는 값이 N 이 홀수일때
이렇게 두가지로 나눌 수 있다.

만일 1번일 경우에는 A타일을 무조건적으로 사용해야 타일을 배치 할 수 있다.
2번일 경우에는 A 타일이 2개 이상일 때 2개를 깐 것이 B타일 1개 깐 것보다 크다면 A 타일 2개를 깔면 될것이고, 작다면 B타일 하나만 까는 것이 이득일 것이다.

📌 코드 설계하기

1. n,a,b를 입력 받는다.
2. 2x1 타일을 tile_A에 2x2 타일을 tile_B 에 저장한다.
3. tile_A와 tile_B를 정렬한다.
4. n이 홀수인지 판별한다.
   • 만일 홀수라면 A 타일을 사용하여 n의 갯수를 -1 줄인다.
5. for 문의 조건을 0 ~ n 까지로 지정하고 타일의 크기가 2 x n 이기 때문에 고정되어 있는 값을 신경 쓰지 말고 n 만 신경써 90 도 돌리는 걸 확인 하면 2씩 증가하게 되면 for문을 성립하게 할 수 있다.
6. index 오류를 방지하기 위해 len(tile_A) 와 len(tile_B) 를 통해 비교 할 수 있는 자료 인지 확인한다.
7. A 타일을 2개 사용한 것이 B 타일 한개 사용 한것보다 컸을때 A 타일 두개를 pop 하고 answer 에 A타일 예쁨 정도 2개를 추가한다.
8. B 타일이 1개가 A 타일 2개 사용한것 보다 컷을때 B 타일 하나를 pop 하고 answer에 B타일 예쁨 정도 1개를 추가한다.
9. for 문을 전부 돌린 후 answer을 출력한다.

📌 시도 회차 수정 사항

1회 틀렸습니다. (sort 함수 실수)

정렬 하는 부분을 잘못 작성해 정렬이 적용되지 않는다.

import sys

n,a,b = map(int,sys.stdin.readline().split())
tile_A = list(map(int,sys.stdin.readline().split())) # 2*1 타일
tile_B = list(map(int,sys.stdin.readline().split())) # 2*2 타일
sorted(tile_A)
sorted(tile_B)
#n이 홀수 일때 -> A 타일을 무조건 사용
#n이 짝수 일때 -> A 타일을 사용하지 않을 수 잇음
answer = 0
if n % 2 == 1: #n이 홀수이면 A타일 무조건 사용
    answer += tile_A[-1]
    tile_A.pop()
    n -= 1

for i in range(0,n,2):
    if len(tile_A) >= 2: #A타일이 2개 이상
        if tile_A[-1] + tile_A[-2] > tile_B[-1]:
            answer += tile_A[-1] + tile_A[-2]
            tile_A.pop()
            tile_A.pop()
        else:
            answer += tile_B[-1]
            tile_B.pop()
    elif len(tile_B) >= 1 and len(tile_A) < 2: # A타일을 2개를 사용하지 못할때
        answer += tile_B[-1]
        tile_B.pop()

print(answer)

2회 틀렸습니다. (런타임 에러 Index Error)

A나 B 배열에 비어 있을때 비교 하기 위해 접근 하는 부분이 index Error를 발생 시키는 문제점을 찾아 if문을 세분화 하여 현재 A와 B 배열이 비교가 가능 할때의 조건을 추가하여 문제를 맞추었다.

📌 정답 코드

import sys

n,a,b = map(int,sys.stdin.readline().split())
tile_A = list(map(int,sys.stdin.readline().split())) # 2*1 타일
tile_B = list(map(int,sys.stdin.readline().split())) # 2*2 타일
tile_A.sort()
tile_B.sort()

#n이 홀수 일때 -> A 타일을 무조건 사용
#n이 짝수 일때 -> A 타일을 사용하지 않을 수 잇음
answer = 0
if n % 2 == 1: #n이 홀수이면 A타일 무조건 사용
    if len(tile_A) >= 1:
        answer += tile_A[-1]
        tile_A.pop()
        n -= 1
for i in range(0,n,2):
    if len(tile_A) >= 2 and len(tile_B) < 1: #A타일이 2개 이상 B타일 사용 불가
        answer += tile_A[-1] + tile_A[-2]
        tile_A.pop()
        tile_A.pop()
    elif len(tile_A) >= 2 and len(tile_B) >= 1: #A타일 2개 이상 B 타일 사용 가능
        if tile_A[-1] + tile_A[-2] >= tile_B[-1]:
            answer += tile_A[-1] + tile_A[-2]
            tile_A.pop()
            tile_A.pop()
        else:
            answer += tile_B[-1]
            tile_B.pop()
    elif len(tile_B) >= 1 and len(tile_A) < 2: # A타일을 2개를 사용하지 못할때
        answer += tile_B[-1]
        tile_B.pop()
print(answer)