[코드트리/Python] 바이러스 검사 & 외주 수익 최대화하기

 

 

1. 바이러스 검사

https://www.codetree.ai/training-field/frequent-problems/problems/virus-detector/description?page=1&pageSize=20&order=tier 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

 

풀이

 

CODE

import sys

input = sys.stdin.readline

num_of_restaurants = int(input())
restaurants = list(map(int, input().split()))
manager, member = map(int, input().split())
total = num_of_restaurants  # 각 식당에 최소 한 명의 매니저 필요

for i in range(num_of_restaurants):
    if restaurants[i] > manager:  # 매니저가 검사 가능한 최대 고객수 보다 많을 때 검사 팀원 필요
        restaurants[i] -= manager
        if restaurants[i] > 0:
            if restaurants[i] % member:
                total += ((restaurants[i] // member) + 1)
            else:
                total += (restaurants[i] // member)

print(total)

 

---

 

2. 외주 수익 최대화하기

https://www.codetree.ai/training-field/frequent-problems/problems/max-of-outsourcing-profit/description?page=1&pageSize=20&order=tier 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

풀이

CODE

import sys

input = sys.stdin.readline
num_of_works = int(input())
works = []

for _ in range(num_of_works):
    works.append(list(map(int, input().split())))

# 방문여부 체크
visited = [False for _ in range(num_of_works)]


def backtracking(idx, ans, result):
	# 현재 index의 외주작업까지 할 수 있는 경우
    if idx + works[idx][0] == num_of_works:
        result.append(ans)
    # 현재 index의 외주작업 기간이 휴가 기간을 초월해서 작업 불가한 경우
    elif idx + works[idx][0] > num_of_works:
        result.append(ans - works[idx][1])

    for i in range(num_of_works):
    	# 현재 외주 작업 이후 다음 index의 외주 작업 찾으러 가기!
        if not visited[i] and idx + works[idx][0] <= i < num_of_works:
            if len(works[i]) == 2:
                visited[i] = True
                # 가능한 경우에 대한 백트래킹 수행
                backtracking(i, ans + works[i][1], result)
                visited[i] = False
            else:
                return ans

    return max(result)


answer = 0
# 시작 지점을 달리하며 최대 수익 찾기
for n in range(num_of_works):
    each = backtracking(n, works[n][1], [])
    if answer < each:
        answer = each

print(answer)

• 장장 15시간 넘게 풀었던 문제
• 백트래킹이 나는 너무 어려운 것 같다. 해결 방법에 감을 잡고도 코드로 나타내기까지 오래 걸렸다.

 

- 끝! -