바이러스 검사

문제 설명

코로나19와 같은 감염병 확산을 막기 위해, 우리는 식당에 방문한 고객들의 체온을 측정해야 합니다.
모든 식당마다 고객의 수가 다르고, 검사자는 검사팀장과 검사팀원으로 나뉘며 검사 가능한 고객 수에 차이가 있습니다.

• 각 식당에는 반드시 검사팀장 1명이 있어야 합니다.

• 검사팀원은 여러 명 있을 수 있으며, 없어도 괜찮습니다.

• 검사자는 자신이 속한 식당의 고객만 검사할 수 있습니다.

이 조건을 만족하며, 모든 고객을 검사하기 위해 필요한 검사자의 최소 수를 구하는 것이 이 문제의 목표입니다.

입력 조건

첫째 줄: 식당 수 n (1 ≤ n ≤ 1,000,000)

둘째 줄: 각 식당의 고객 수 c[i] (1 ≤ c[i] ≤ 1,000,000)

셋째 줄: 검사팀장 a, 검사팀원 b가 검사할 수 있는 최대 고객 수 (1 ≤ a, b ≤ 1,000,000)

출력 조건

모든 식당 고객을 검사하기 위해 필요한 최소 검사자 수를 출력합니다.

문제 접근

이 문제는 그리디 알고리즘(탐욕법)으로 접근할 수 있습니다.
각 식당에 대해 다음과 같은 절차를 따르면 됩니다:

• 무조건 검사팀장 1명을 배치합니다.

• 검사팀장이 검사할 수 있는 만큼(a명) 우선 검사합니다.

• 남은 고객 수에 대해 검사팀원을 필요한 만큼 배치합니다.

• 팀원은 한 명당 최대 b명까지 검사할 수 있으므로, 남은 고객 수를 b로 나누고, 나머지가 있다면 한 명 더 추가합니다.

코드

n = int(input())  # 식당 수
c = list(map(int, input().split()))  # 각 식당의 고객 수
a, b = map(int, input().split())  # 팀장, 팀원이 검사 가능한 최대 고객 수

def check(n, c, a, b):
    total = 0  # 총 필요한 검사자 수

    for i in range(len(c)):
        # 각 식당마다 팀장 1명은 무조건 필요
        total += 1
        c[i] -= a  # 팀장이 검사한 만큼 빼기

        if c[i] > 0:
            # 팀원 필요한 수 계산
            count = c[i] // b
            if c[i] % b > 0:
                count += 1
            total += count  # 팀원 수 더하기

    return total

print(check(n, c, a, b))

마무리
이 문제의 핵심은 각 식당에 반드시 팀장 1명은 필요하다는 조건을 빠뜨리지 않는 것입니다.
그 외에는 고객 수에 따라 필요한 만큼의 팀원을 나누어 배치하면 되는 단순한 그리디 문제입니다.

처음에는 단순한 반복문만으로 해결 가능하다는 점에서 접근성이 좋고, 입력 크기가 크기 때문에 효율적인 구현이 중요합니다.

외주 수익 최대화

문제 설명

어느 개발자가 n일간의 휴가를 갖게 되었습니다.
이 휴가 기간 동안 외주 개발 작업을 수행해 수익을 최대화하려고 합니다.

• 매일 하나의 외주 작업이 주어지며, 각 작업은 수행에 필요한 기간 t와 작업을 완료했을 때의 수익 p가 주어집니다.

• 외주 작업은 동시에 여러 개를 수행할 수 없습니다.

• 작업이 휴가 기간을 넘겨서 끝나는 경우, 수행할 수 없습니다.

입력 형식

• 첫째 줄: 휴가 일 수 n (1 ≤ n ≤ 15)

• 이후 n개의 줄: 각 줄에 외주 작업의 기간 t와 수익 p (1 ≤ t ≤ 5, 1 ≤ p ≤ 1000)

예제 입력

2
2 5
1 4

[예제 설명]
1일차 작업은 2일이 걸리고 수익은 5

2일차 작업은 1일이 걸리고 수익은 4

최대 수익은 1일차 작업 하나만 수행하여 5입니다. (2일차 작업을 하게 되면 1일차 작업을 못하므로 총 수익이 더 낮아짐)

문제 접근 방식

이 문제는 모든 작업의 조합을 탐색하면서 가능한 경우 중에서 수익이 최대가 되는 조합을 찾아야 합니다.
이때 백트래킹(Backtracking) 을 활용하면 효율적으로 탐색할 수 있습니다.

백트래킹 탐색 방법

• selected_jobs 리스트에 현재 선택한 외주 작업 인덱스를 저장합니다.

• 탐색 도중 조건에 맞지 않는 작업 조합이면 더 이상 탐색하지 않고 돌아갑니다.

• 조건을 만족한다면 현재 수익을 계산하여 max_profit을 갱신합니다.

[핵심 조건]
1. 각 작업은 겹치지 않아야 하며, 작업 기간이 끝나는 날이 휴가일 n일을 넘으면 안 됩니다.
2. 작업들의 시작일과 종료일을 미리 계산해두고 조건에 맞는 조합만 탐색해야 합니다.

n = int(input())

# 외주 작업의 (기간, 수익) 리스트
given_time_profits = [
    tuple(map(int, input().split()))
    for _ in range(n)
]

# 각 외주 작업의 (시작일, 종료일) 계산
times = [
    (i, i + time - 1)
    for i, (time, _) in 
    enumerate(given_time_profits, start=1)
]

profits = [
    profit 
    for _, profit in given_time_profits
]

selected_jobs = []
max_profit = 0

# 선택한 외주 작업의 총 수익 계산
def get_profit():
    return sum([
        profits[job_idx]
        for job_idx in selected_jobs
    ])

# 현재 선택한 작업들이 조건에 맞는지 검사
def is_available():
    # 외주 작업 간의 시간 겹침 체크
    for i in range(len(selected_jobs) - 1):
        _, end_time = times[selected_jobs[i]]
        start_time, _ = times[selected_jobs[i + 1]]
        if end_time >= start_time:
            return False
    
    # 각 작업의 종료일이 n일 이내인지 체크
    for job_idx in selected_jobs:
        _, end_time = times[job_idx]
        if end_time > n:
            return False
    
    return True

# 백트래킹 탐색
def find_max_profit(curr_idx):
    global max_profit

    # 모든 날짜 탐색 완료
    if curr_idx == n:
        if is_available():
            max_profit = max(max_profit, get_profit())
        return
    
    # 현재 작업을 수행하지 않을 경우
    find_max_profit(curr_idx + 1)
    
    # 현재 작업을 수행할 경우
    selected_jobs.append(curr_idx)
    find_max_profit(curr_idx + 1)
    selected_jobs.pop()

# 탐색 시작
find_max_profit(0)
print(max_profit)