그리디

예제 1

백준의 동전 0 문제가 대표적인 그리디 문제다.

• 리스트: 동전 목록
• 조건: 금액
• 조합 최적해: 동전 조합 중 최소 개수

예제 2

[분할 가능 냅색 알고리즘]이 여기에 해당한다.

• 리스트: 무게 당 가치
• 조건: 무게 한도
• 조합 최적해: 냅색 조합 중 최대 가치

설계

• 리스트를 생성하기 위해 반복문을 사용했다.

그리디 구현 아이디어

• 여분 학생 기준으로 무조건 왼쪽부터 탐색한다.
• 왼쪽이 도난 학생이 아닐 시 오른쪽을 탐색한다.
• 둘다 도난 학생이 아니라면 넘어간다.

코드

def solution(n, lost, reserve):
    answer = -1
    clothes = [1]*(n+1)
    for l in lost:
        clothes[l] -= 1
    for r in reserve:
        clothes[r] += 1
    for i in range(1,n+1):
        if clothes[i] == 2:
            if 1<=i-1 and clothes[i-1] == 0:
                clothes[i-1] += 1
                clothes[i] -= 1
            elif i+1<=n and clothes[i+1] == 0:
                clothes[i+1] += 1
                clothes[i] -= 1
            else:
                continue
    for c in clothes:
        if c:
            answer += 1
    return answer