์๋ด์์ผ๋ก ์ผํ๊ณ ์๋ ๋ฐฑ์ค์ด๋ ํด์ฌ๋ฅผ ํ๋ ค๊ณ ํ๋ค.
์ค๋๋ถํฐ N+1์ผ์งธ ๋๋ ๋ ํด์ฌ๋ฅผ ํ๊ธฐ ์ํด์, ๋จ์ N์ผ ๋์ ์ต๋ํ ๋ง์ ์๋ด์ ํ๋ ค๊ณ ํ๋ค.
๋ฐฑ์ค์ด๋ ๋น์์๊ฒ ์ต๋ํ ๋ง์ ์๋ด์ ์ก์ผ๋ผ๊ณ ๋ถํ์ ํ๊ณ , ๋น์๋ ํ๋ฃจ์ ํ๋์ฉ ์๋ก ๋ค๋ฅธ ์ฌ๋์ ์๋ด์ ์ก์๋์๋ค.
๊ฐ๊ฐ์ ์๋ด์ ์๋ด์ ์๋ฃํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ๊ธฐ๊ฐ Ti์ ์๋ด์ ํ์ ๋ ๋ฐ์ ์ ์๋ ๊ธ์ก Pi๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
N = 7์ธ ๊ฒฝ์ฐ์ ๋ค์๊ณผ ๊ฐ์ ์๋ด ์ผ์ ํ๋ฅผ ๋ณด์.
1์ผ 2์ผ 3์ผ 4์ผ 5์ผ 6์ผ 7์ผ
Ti 3 5 1 1 2 4 2
Pi 10 20 10 20 15 40 200
1์ผ์ ์กํ์๋ ์๋ด์ ์ด 3์ผ์ด ๊ฑธ๋ฆฌ๋ฉฐ, ์๋ดํ์ ๋ ๋ฐ์ ์ ์๋ ๊ธ์ก์ 10์ด๋ค. 5์ผ์ ์กํ์๋ ์๋ด์ ์ด 2์ผ์ด ๊ฑธ๋ฆฌ๋ฉฐ, ๋ฐ์ ์ ์๋ ๊ธ์ก์ 15์ด๋ค.
์๋ด์ ํ๋๋ฐ ํ์ํ ๊ธฐ๊ฐ์ 1์ผ๋ณด๋ค ํด ์ ์๊ธฐ ๋๋ฌธ์, ๋ชจ๋ ์๋ด์ ํ ์๋ ์๋ค. ์๋ฅผ ๋ค์ด์ 1์ผ์ ์๋ด์ ํ๊ฒ ๋๋ฉด, 2์ผ, 3์ผ์ ์๋ ์๋ด์ ํ ์ ์๊ฒ ๋๋ค. 2์ผ์ ์๋ ์๋ด์ ํ๊ฒ ๋๋ฉด, 3, 4, 5, 6์ผ์ ์กํ์๋ ์๋ด์ ํ ์ ์๋ค.
๋ํ, N+1์ผ์งธ์๋ ํ์ฌ์ ์๊ธฐ ๋๋ฌธ์, 6, 7์ผ์ ์๋ ์๋ด์ ํ ์ ์๋ค.
ํด์ฌ ์ ์ ํ ์ ์๋ ์๋ด์ ์ต๋ ์ด์ต์ 1์ผ, 4์ผ, 5์ผ์ ์๋ ์๋ด์ ํ๋ ๊ฒ์ด๋ฉฐ, ์ด๋์ ์ด์ต์ 10+20+15=45์ด๋ค.
์๋ด์ ์ ์ ํ ํ์ ๋, ๋ฐฑ์ค์ด๊ฐ ์ป์ ์ ์๋ ์ต๋ ์์ต์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N (1 โค N โค 15)์ด ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ Ti์ Pi๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด์ ์ฃผ์ด์ง๋ฉฐ, 1์ผ๋ถํฐ N์ผ๊น์ง ์์๋๋ก ์ฃผ์ด์ง๋ค. (1 โค Ti โค 5, 1 โค Pi โค 1,000)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฐฑ์ค์ด๊ฐ ์ป์ ์ ์๋ ์ต๋ ์ด์ต์ ์ถ๋ ฅํ๋ค.
๋ ์ง๊ฐ n์ ๋์ด๊ฐ๋ฉด ์๋จ
์ง๊ธ๊น์ง ๋์จ ์ต๋ ์ด์ต์ ์ ์งํด์ผํจ
์ต๋ ์ด์ต์ ์ด์ ๋ ์ง์์์ ์ด์ต + ์ป์ ์ด์ต, ์ง๊ธ์ ์ด์ต์ ๋น๊ตํด์ ๋ ํฐ ๊ฐ์
1) ๋ ์ง๊ฐ n์ ๋์ด๊ฐ๋ฉด ์๋จ
int day = i+t[i];
if(day <= n)
2) ์ง๊ธ๊น์ง์ ์ต๋์ด์ต์ ์ ์งํจ
dp[i+1] = Math.max(dp[i], dp[i+1]);
3) ์ง๊ธ ์ด์ต VS ๊ธฐ์กด ์ด์ต + ์ป์ ์ด์ต
dp[day] = Math.max(dp[day], dp[i] + p[i]);
import java.io.*;
public class DP_2 {
static int p[],t[], dp[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
p = new int[n];
t = new int[n];
dp = new int[n+1];
for(int i=0; i<n; i++) {
String s[] = br.readLine().split(" ");
t[i] = Integer.parseInt(s[0]);
p[i] = Integer.parseInt(s[1]);
}
System.out.println(out(n));
}
static int out(int n) {
int max = 0;
for(int i=0; i<n; i++) {
int day = i+t[i];
if(day <= n)
dp[day] = Math.max(dp[i]+p[i], dp[day]);
dp[i+1] = Math.max(dp[i+1], dp[i]);
}
return dp[n];
}
}
์ฑ๊ณต~