14501번 퇴사, 15486번 퇴사 2

퇴사 = https://www.acmicpc.net/problem/14501

퇴사 2 = https://www.acmicpc.net/problem/15486

나중에 다시 풀어볼 문제이다. DP 연습에 좋다. 복습.

14501번 퇴사 문제의 경우 3가지 코드를 올리겠다.(사실상 2가지)

2번 코드처럼 N부터 시작하여 1로 가는 하향식 접근도 기억해야겠다.

3번 코드의 28번 째 줄이 n+1인 이유는 

다음과 같은 이유가 있기 때문이다.

3

1 1

1 2

1 3

오답 : 3

정답 : 6

3 + T[3] = 4(n+1은 4이기 때문에 if문 진행)가 되고, 

backtracking(4) + P[3]에서 P[3]의 값도 구해야하기 때문(backtracking(4)는 0으로 return)이다.

참고로, n+1이 아니라 그냥 n으로 쓰면 P[3]이 계산에서 제외된다.

3 + T[3] = 4이고, 4 <= 3으로 if문이 실행되지 않는다.

1. 14501번 퇴사 문제 DP - 1(참고로 15486번 퇴사 2 문제는 시간 초과)

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
/*
dp[i] = i번 째 일까지 얻을 수 있는 최대 금액

j = 1 ~ i-1
dp[i번 째 일] = max(dp[i번 째 일], i번 째 금액 + dp[j])

dp[i] = max(dp[i], P[i] + dp[j])
*/
 
int dp[1500005] = { 0, }, T[1500005] = { 0, }, P[15000005] = { 0, };
 
int main(void)
{
    int day = 0, money = 0, N = 0;
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d %d", &day, &money);
 
        T[i] = day; P[i] = money; dp[i] = P[i];
    }
 
    for (int i = 2; i <= N; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (i - j >= T[j])
            {
                dp[i] = max(dp[i], dp[j] + P[i]);
 
            }
        }
    }
 
    int ans = 0;
 
    /*
    ans = -1로 하면,
    1
    2 1
    반례에 걸린다
    */
 
    for (int i = 1; i <= N; i++) if (i + T[i] <= N + 1) ans = max(ans, dp[i]);
 
    printf("%d\n", ans);
    
    return 0;
}

2. 14501번 퇴사 문제 DP - 2 및 15486번 퇴사 2 문제 정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int dp[1500005] = { 0, }, T[1500005] = { 0, }, P[15000005] = { 0, };
 
int main(void)
{
    int day = 0, money = 0, N = 0;
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d %d", &day, &money);
        T[i] = day; P[i] = money;
    }
 
    for (int i = N; i >= 1; i--)
        if (i + T[i] > N + 1) dp[i] = dp[i + 1];    
        else dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]]);
 
    printf("%d\n", dp[1]);
    
    return 0;
}

3. 14501번 퇴사 문제 백트래킹

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int dp[16] = { 0, }, T[16] = { 0, }, P[16] = { 0, }, N = 0;
 
int backtracking(int n)
{
    if (n > N) return 0;
 
    int ret = 0;
 
    if (n + T[n] <= N + 1) ret = max(ret, backtracking(n + T[n]) + P[n]);    
 
    ret = max(ret, backtracking(n + 1));
 
    return ret;
}
 
int main(void)
{
    int day = 0, money = 0;
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d %d", &day, &money);
        T[i] = day; P[i] = money;
    }
 
    printf("%d\n", backtracking(1));
    
    return 0;
}