[ c++ ][ Python ] 퇴사

 

처음에 문제를 읽고나서 가장 먼저 든 생각은 DFS면 풀리겠다 였다.

생각대로 i번째 날짜에서 상담을 하는 경우와 하지 않는 경우로 나누면 답을 빨리 구할 수 있었다.

이 경우 N이 최대 15이기 때문에 재귀로 문제를 풀어도 문제가 발생하지 않는다. 

 

  DFS code

• C++

#include <iostream>
#define MAXSZ 17

using namespace std;

int N, res = -1;
int day[MAXSZ];
int price[MAXSZ];

void solve(int cur, int sum) {
	if (cur == N) {
		if (res < sum)
			res = sum;
		return;
	}
	else if (cur > N)
		return;

	solve(cur + 1, sum);
	solve(cur + day[cur], sum + price[cur]);
}

int main() {
	ios_base::sync_with_stdio(false);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> day[i] >> price[i];
	}

	solve(0, 0);

	cout << res;
	return 0;
}

• python

import sys

N = int(input())
day = [0]*20
price = [0]*20
res = -1

for i in range(0, N):
    day[i], price[i] = map(int, sys.stdin.readline().strip().split(" "))
    #day[i], price[i] = map(int,input().split())

def solve(cur, sum):
    global res
    if (cur == N) :
        res = max(res, sum)
        return
    elif (cur > N) :
        return

    solve(cur + day[cur], sum + price[cur])
    solve(cur+1, sum)

solve(0,0)
print(res)

 

 

  DP code

 

이 문제를 DP로 풀기 위해서 생각하는 과정에서 많은 문제가 있었다.

처음에 DP[i] = i일에서의 최대 금액 을 맞추기 위해 O(N^2)의 방법을 생각했다. 하지만 과정을 잘 생각해보니 for문 한 번으로 DP에 모두 기록할 수 있었다.

• C++

#include <iostream>
#include <algorithm>
#define MAXSZ 20

using namespace std;

int day[MAXSZ];
int price[MAXSZ];
int dp[MAXSZ];

int main() {
	ios_base::sync_with_stdio(false);

	int N, res = 0;

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> day[i] >> price[i];
	}

	for (int i = 1; i <= N + 1; i++) {
		dp[i] = max(dp[i], res);
		dp[day[i] + i] = max(dp[day[i] + i], price[i] + dp[i]);
		res = dp[i];
	}
    
	cout << res;
	return 0;
}

i 번째 날에 최대 금액은 현재 최대값, dp[i] 중에 하나이다.

( i번째 날 + 상담기간 ) 인 날에 최대 금액은 ( 해당 날짜의 최대값 ), ( i번째 날의 최대값 + i번째날의 금액 ) 중 하나이므로 이를 dp에 갱신해준다.

 

• python