๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ฒ์์ ๊ณ๋จ ์๋ ์์์ ๋ถํฐ ๊ณ๋จ ๊ผญ๋๊ธฐ์ ์์นํ ๋์ฐฉ์ ๊น์ง ๊ฐ๋ ๊ฒ์์ด๋ค. <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ๊ฐ๊ฐ์ ๊ณ๋จ์๋ ์ผ์ ํ ์ ์๊ฐ ์ฐ์ฌ ์๋๋ฐ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด ๊ทธ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๋ฅผ ์ป๊ฒ ๋๋ค.
์๋ฅผ ๋ค์ด <๊ทธ๋ฆผ 2>์ ๊ฐ์ด ์์์ ์์๋ถํฐ ์ฒซ ๋ฒ์งธ, ๋ ๋ฒ์งธ, ๋ค ๋ฒ์งธ, ์ฌ์ฏ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ์ ๋์ฐฉ์ ์ ๋๋ฌํ๋ฉด ์ด ์ ์๋ 10 + 20 + 25 + 20 = 75์ ์ด ๋๋ค.
๊ณ๋จ ์ค๋ฅด๋ ๋ฐ๋ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ด ์๋ค.
1.๊ณ๋จ์ ํ ๋ฒ์ ํ ๊ณ๋จ์ฉ ๋๋ ๋ ๊ณ๋จ์ฉ ์ค๋ฅผ ์ ์๋ค. ์ฆ, ํ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด์ ์ด์ด์ ๋ค์ ๊ณ๋จ์ด๋, ๋ค์ ๋ค์ ๊ณ๋จ์ผ๋ก ์ค๋ฅผ ์ ์๋ค.
2.์ฐ์๋ ์ธ ๊ฐ์ ๊ณ๋จ์ ๋ชจ๋ ๋ฐ์์๋ ์ ๋๋ค. ๋จ, ์์์ ์ ๊ณ๋จ์ ํฌํจ๋์ง ์๋๋ค.
3.๋ง์ง๋ง ๋์ฐฉ ๊ณ๋จ์ ๋ฐ๋์ ๋ฐ์์ผ ํ๋ค.
๋ฐ๋ผ์ ์ฒซ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ณ ์ด์ด ๋ ๋ฒ์งธ ๊ณ๋จ์ด๋, ์ธ ๋ฒ์งธ ๊ณ๋จ์ผ๋ก ์ค๋ฅผ ์ ์๋ค. ํ์ง๋ง, ์ฒซ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ณ ์ด์ด ๋ค ๋ฒ์งธ ๊ณ๋จ์ผ๋ก ์ฌ๋ผ๊ฐ๊ฑฐ๋, ์ฒซ ๋ฒ์งธ, ๋ ๋ฒ์งธ, ์ธ ๋ฒ์งธ ๊ณ๋จ์ ์ฐ์ํด์ ๋ชจ๋ ๋ฐ์ ์๋ ์๋ค.
๊ฐ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๊ฐ ์ฃผ์ด์ง ๋ ์ด ๊ฒ์์์ ์ป์ ์ ์๋ ์ด ์ ์์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ์งธ ์ค์ ๊ณ๋จ์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ ์ผ ์๋์ ๋์ธ ๊ณ๋จ๋ถํฐ ์์๋๋ก ๊ฐ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ณ๋จ์ ๊ฐ์๋ 300์ดํ์ ์์ฐ์์ด๊ณ , ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๋ 10,000์ดํ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ฒ์์์ ์ป์ ์ ์๋ ์ด ์ ์์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
3๋ฒ ์ฐ์ X โ 1 or 2์นธ๋ง ๊ฐ๋ค
dp[i] = Math.max(dp[i-3]+score[i]+score[i-1], dp[i-2]+score[i]);
import java.io.*;
import java.util.*;
public class DP_4 {
static int n;
static int score[], dp[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
score = new int[n+1];
dp = new int[n+1];
for(int i=1; i<=n; i++)
score[i] = Integer.parseInt(br.readLine());
dp[1] = score[1];
if(n>=2) dp[2] = dp[1]+score[2];
for(int i=3; i<=n; i++) {
dp[i] = Math.max(dp[i-3]+score[i]+score[i-1], dp[i-2]+score[i]);
}
System.out.println(dp[n]);
}
}
์ฑ๊ณต~