그리디 알고리즘

1. 백준 회의실배정

https://www.acmicpc.net/problem/1931

- 주어진 회의 일정들을 회의실 하나에서 최대한 많이 배정하는 것이 목표

- 주요 아이디어는 빨리 끝나는 회의를 먼저 선택하는 것

• 빨리 끝나는 회의를 먼저 배정하면 남은 시간 동안 더 많은 회의를 배치할 수 있습니다.
• 따라서 종료 시간이 빠른 회의부터 배정하면, 회의가 겹치지 않으면서 최대한 많은 회의를 배정할 수 있습니다.

import sys
input = sys.stdin.read

def max_meetings(meetings):
    # 종료 시간을 기준으로 오름차순 정렬 (종료 시간이 같으면 시작 시간 기준)
    meetings.sort(key=lambda x: (x[1], x[0]))
    
    count = 0
    last_end_time = 0  # 마지막으로 배정된 회의의 종료 시간
    
    for start, end in meetings:
        # 현재 회의의 시작 시간이 마지막 회의 종료 시간 이후인 경우에만 배정
        if start >= last_end_time:
            count += 1
            last_end_time = end  # 마지막 종료 시간 갱신
            
    return count

 

 

2. 백준 폴리오미노

https://www.acmicpc.net/problem/1343

 

X의 연속 개수 세기가 핵심.. X를 마주쳤을때, while문을 다시 돌려서 갯수 카운팅

def polynomio(board):
    result = ""
    i = 0
    n = len(board)
    
    while i < n:
        if board[i] == 'X':
            x_count = 0
            # 연속된 X 개수 세기
            while i < n and board[i] == 'X':
                x_count += 1
                i += 1
            
            # 홀수 개의 X가 있으면 -1 반환
            if x_count % 2 != 0:
                return -1

            # 짝수 개의 X 처리
            # 4의 배수는 AAAA로 채우고, 나머지는 BB로 채우기
            result += 'AAAA' * (x_count // 4) + 'BB' * ((x_count % 4) // 2)
        
        else:
            # X가 아닐 경우(즉, .일 경우) 그대로 추가
            result += board[i]
            i += 1
    
    return result

# 입력 예시
board = input().strip()
print(polynomio(board))