> For the complete documentation index, see [llms.txt](https://pyohamen.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://pyohamen.gitbook.io/til/algorithm/boj/14501.md).

# 14501

## 14501-퇴사

> [www.acmicpc.net/problem/14501](https://www.acmicpc.net/problem/14501)

## 브루트 포스

1. s\_index 는 순열로 인덱스를 뽑을 때 사용할 인덱스순서대로 인덱스가 들어있는 배열
2. 우선 1개를 뽑는 경우부터 n 개 모두를 뽑는 반복문
3. 뽑을 개수만큼 순열로 뽑을 인덱스들을 추출
4. 뽑은 인덱스에 대해서 상담이 가능한지 확인
5. 가능하다면 해당의 금액 최댓값 업데이트

```python
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] 를 더한 것과, 현재까지의 최댓값을 비교하면서 취해감

```python
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)
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://pyohamen.gitbook.io/til/algorithm/boj/14501.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.