Game Develop

[Algorithm]Baekjoon 15486번 : 퇴사 2 본문

Algorithm/Baekjoon

[Algorithm]Baekjoon 15486번 : 퇴사 2

MaxLevel 2023. 12. 13. 03:13

https://www.acmicpc.net/problem/15486

 

15486번: 퇴사 2

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
int n, a, b;
 
int days[1500001= { 0 };
int moneys[1500001= { 0 };
int dp[1500001= { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> days[i] >> moneys[i];
    }
 
    for (int i = 1; i <= n + 1++i)
    {
        if (i + days[i] <= n + 1)
        {
            dp[i + days[i]] = max(dp[i + days[i]], dp[i] + moneys[i]);
        }
        
        dp[i + 1= max(dp[i], dp[i + 1]);
    }
 
    cout << dp[n + 1];
}
cs

 

예전에 풀어봤던 퇴사 문제에서 n값이 더 커진 문제이다.

퇴사문제에서 O(n)으로 풀었었다면 그냥 배열크기만 바꾼다음 그대로 제출하면 된다.

 

이 문제의 dp업데이트의 특징?은 현재 날짜에 주어진 값으로 나중의 날짜에 해당하는 dp테이블을 업데이트 하는것이다.

왜냐하면 현재 날짜에 주어진 일을 접수하면, 일정 기간 이후에 보수가 지급되기 때문이다.

만약 i 번째일에 주어지는 업무가 3일이 걸린다면, i번째일까지의 최대보수 + i번째업무보수의 값을 dp[i+3]에 업데이트 하는 것이다.

즉, 일단 dp[i]는 i번째 일까지의 최대 보수이다.

거기에 더해서 현재날짜의 dp값을 다음날짜 dp값에 업데이트하려는 시도도 해야 한다.

왜냐하면 i번째날짜까지의 최대보수값은 곧 i+1번째날짜까지의 최대보수값이 될 수 있기 때문이다.

 

마지막으로 n이 아니라 n+1까지 업데이트하는 이유는, n번째 날에 1일짜리 업무를 맡을 경우 퇴사날인 n+1번째날에 보수를 받을 수 있기 때문이다. 이 점을 문제에 명시하면 더 좋았을 것 같다.