ํจ์ฃผ๋ ํฌ๋์ฃผ ์์ํ์ ๊ฐ๋ค. ๊ทธ ๊ณณ์ ๊ฐ๋๋, ํ ์ด๋ธ ์์ ๋ค์ํ ํฌ๋์ฃผ๊ฐ ๋ค์ด์๋ ํฌ๋์ฃผ ์์ด ์ผ๋ ฌ๋ก ๋์ฌ ์์๋ค. ํจ์ฃผ๋ ํฌ๋์ฃผ ์์์ ํ๋ ค๊ณ ํ๋๋ฐ, ์ฌ๊ธฐ์๋ ๋ค์๊ณผ ๊ฐ์ ๋ ๊ฐ์ง ๊ท์น์ด ์๋ค.
1.ํฌ๋์ฃผ ์์ ์ ํํ๋ฉด ๊ทธ ์์ ๋ค์ด์๋ ํฌ๋์ฃผ๋ ๋ชจ๋ ๋ง์ ์ผ ํ๊ณ , ๋ง์ ํ์๋ ์๋ ์์น์ ๋ค์ ๋์์ผ ํ๋ค.
2.์ฐ์์ผ๋ก ๋์ฌ ์๋ 3์์ ๋ชจ๋ ๋ง์ค ์๋ ์๋ค.
ํจ์ฃผ๋ ๋ ์ ์๋ ๋๋ก ๋ง์ ์์ ํฌ๋์ฃผ๋ฅผ ๋ง๋ณด๊ธฐ ์ํด์ ์ด๋ค ํฌ๋์ฃผ ์์ ์ ํํด์ผ ํ ์ง ๊ณ ๋ฏผํ๊ณ ์๋ค. 1๋ถํฐ n๊น์ง์ ๋ฒํธ๊ฐ ๋ถ์ด ์๋ n๊ฐ์ ํฌ๋์ฃผ ์์ด ์์๋๋ก ํ ์ด๋ธ ์์ ๋์ฌ ์๊ณ , ๊ฐ ํฌ๋์ฃผ ์์ ๋ค์ด์๋ ํฌ๋์ฃผ์ ์์ด ์ฃผ์ด์ก์ ๋, ํจ์ฃผ๋ฅผ ๋์ ๊ฐ์ฅ ๋ง์ ์์ ํฌ๋์ฃผ๋ฅผ ๋ง์ค ์ ์๋๋ก ํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์๋ฅผ ๋ค์ด 6๊ฐ์ ํฌ๋์ฃผ ์์ด ์๊ณ , ๊ฐ๊ฐ์ ์์ ์์๋๋ก 6, 10, 13, 9, 8, 1 ๋งํผ์ ํฌ๋์ฃผ๊ฐ ๋ค์ด ์์ ๋, ์ฒซ ๋ฒ์งธ, ๋ ๋ฒ์งธ, ๋ค ๋ฒ์งธ, ๋ค์ฏ ๋ฒ์งธ ํฌ๋์ฃผ ์์ ์ ํํ๋ฉด ์ด ํฌ๋์ฃผ ์์ด 33์ผ๋ก ์ต๋๋ก ๋ง์ค ์ ์๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํฌ๋์ฃผ ์์ ๊ฐ์ n์ด ์ฃผ์ด์ง๋ค. (1โคnโค10,000) ๋์งธ ์ค๋ถํฐ n+1๋ฒ์งธ ์ค๊น์ง ํฌ๋์ฃผ ์์ ๋ค์ด์๋ ํฌ๋์ฃผ์ ์์ด ์์๋๋ก ์ฃผ์ด์ง๋ค. ํฌ๋์ฃผ์ ์์ 1,000 ์ดํ์ ์์ด ์๋ ์ ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ต๋๋ก ๋ง์ค ์ ์๋ ํฌ๋์ฃผ์ ์์ ์ถ๋ ฅํ๋ค.
์ด 3๊ฐ์ง๋ก ๋๋์ด์ ๊ณ์ฐ
1) ํ์ฌ ํฌ๋์ฃผ X
2) ํ์ฌ ํฌ๋์ฃผ O, ์ด์ ํฌ๋์ฃผ X
3) ํ์ฌ ํฌ๋์ฃผ O, ์ด์ ํฌ๋์ฃผ O
1) ํ์ฌ ํฌ๋์ฃผ X
dp[i-1]
2) ํ์ฌ ํฌ๋์ฃผ O, ์ด์ ํฌ๋์ฃผ X
dp[i-2]+p[i]
3) ํ์ฌ ํฌ๋์ฃผ O, ์ด์ ํฌ๋์ฃผ O
dp[i-3] + p[i] + p[i-2]
import java.util.Scanner;
public class DP_3 {
static int p[];
static int dp[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
p = new int[n+10];
dp = new int[n+10];
for(int i=1; i<=n; i++)
p[i] = sc.nextInt();
dp[1] = p[1];
dp[2] = p[1]+p[2];
System.out.println(maxWine(n));
}
static int maxWine(int n) {
for(int i=3; i<=n; i++) {
int ret = 0;
ret = Math.max(p[i]+dp[i-2], dp[i-1]);
ret = Math.max(ret, dp[i-3]+p[i-1]+p[i]);
dp[i] = ret;
}
return dp[n];
}
}
์ฑ๊ณต~