[알고리즘] 퇴사

포인트

1. 완전탐색 방법과 다이나믹 방법이 있다. 

2. 완전 탐색 방법은 재귀를 통해서 구한다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

브루트포스

#include <iostream>

using namespace std;
int n;
int time[16];
int cost[16];
int value = 0;

void go(int index, int v) {
    if (index > n) return; // 조건을 넘을 떄

    if (index == n) { // 조건을 만족할 때
        value = max(value, v);
        return;
    }

    go(index + time[index], v + cost[index]); //상담을 할 때
    go(index + 1, v); // 상담을 안하고 넘어갈때
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> time[i] >> cost[i];
    }

    go(0, 0);

    cout << value << '\n';
    return 0;
}

다이나믹

#include <iostream>
#include <algorithm>

using namespace std;

int d[16];
int time[16];
int cost[16];
int n;

//dp의 경우
int go(int day) {
    if (day == n + 1) return 0;
    //날짜가 n+1보다 크다면 -값을 크게 준다.
    if (day > n + 1) return -987654321;
    //메모이제이션
    if (d[day] > 0) return d[day];
    //점화식 상담을 안한다 혹은 상담을 한다. 둘 중 하나를 고른다.
    return d[day] = max(go(day + 1), go(day + time[day]) + cost[day]); //재귀가 들어감
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> time[i] >> cost[i];

    // 입력을 하는 부분
    cout << go(1) << "\n";

    return 0;
}

 

2021 03 07 수정

import sys

sys.stdin = open('input.txt')


def go(index: int, val: int):
    global max_value
    if index == n:
        max_value = max(max_value, val)
        return

    if index >= n:
        return

    go(index + data[index][0], val + data[index][1])

    go(index + 1, val)


n = int(input())

data = []
for _ in range(n):
    a, b = map(int, input().split())
    data.append([a, b])

max_value = 0

go(0, 0)

print(max_value)