14501

14501-퇴사

www.acmicpc.net/problem/14501

브루트 포스

1. s_index 는 순열로 인덱스를 뽑을 때 사용할 인덱스순서대로 인덱스가 들어있는 배열

2. 우선 1개를 뽑는 경우부터 n 개 모두를 뽑는 반복문

3. 뽑을 개수만큼 순열로 뽑을 인덱스들을 추출

4. 뽑은 인덱스에 대해서 상담이 가능한지 확인

5. 가능하다면 해당의 금액 최댓값 업데이트

from itertools import combinations

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s_index = [i for i in range(n)]

def check(indexs):
    global money, n
    # 순열로 뽑은 인덱스만 값을 할당한다
    temp = [0 for i in range(n)]
    for index in indexs:
        temp[index] = a[index]

    # temp 가능한 배치인지 검사
    for i in range(len(temp)):
        index = i
        if temp[i]:
            long = temp[i][0]
            # 인덱싱 범위가 넘어가진 않는지
            if index + long > n:
                return False
            # 오늘부터 상당하는 동안 아무도 안 오는지
            for j in range(1, long):
                if temp[index + j]:
                    return False

    # 가능해서 여기까지 왔으니 돈계산을 해주자
    money = 0
    for i in range(len(indexs)):
        money += a[indexs[i]][1]
    return True

max_answer = 0
money = 0
# 1 개를 고르는 것 부터 N 개를 전부 고르는 순열들
for pic_num in range(1, n + 1):
    # 인덱스들 중에서 몇 개 고를지 만큼 만큼 순열로 뽑아주자
    pic_combination = list(combinations(s_index,pic_num))
    # pics 는 내가 고를 인덱스들
    for pics in pic_combination:
        # 해당 인덱스들을 골랐을 때 가능한지 확인하자
        if check(pics):
            # 가능했다면 최댓값 업데이트
            max_answer = max(max_answer,money)

print(max_answer)

다이나믹 프로그래밍

• 점화식

  dp[i] = max(p[i] + d[t[i] + i], max_p)

• 끝에서부터 매번 선택해나갈 때, 지금것을 취하고, 지금 것 상담이 끝난 후의 dp[i] 를 더한 것과, 현재까지의 최댓값을 비교하면서 취해감

n = int(input())

# 0 번째 날은 의미가 없으니 0으로 넣어주고, 인덱싱을 일차랑 맞추기 위해
t = [0]
p = [0]

for i in range(n):
    a, b = map(int,input().split())
    t.append(a)
    p.append(b)

d = [0] * (n + 1)
max_p = 0

# 인덱스 n 부터 하나씩 뺴가면서 1까지
for i in range(n, 0, -1):

    # 애초에 현재 것이 퇴사날 전까지 가능한지 검증
    if t[i] + i <= n + 1:
        #
        if i + t[i] > n:
            f = 0
        else:
            f = d[i + t[i]]
        d[i] = max(p[i] + f, max_p)
        max_p = d[i]
    else:
        d[i] = max_p

print(max_p)