์์ฆ ๋ฏผ๊ท๋ค ๋๋ค์์๋ ์คํํธ๋งํฌ์์ ๋ง๋ PS์นด๋๋ฅผ ๋ชจ์ผ๋ ๊ฒ์ด ์ ํ์ด๋ค.
PS์นด๋๋ PS(Problem Solving)๋ถ์ผ์์ ์ ๋ช ํ ์ฌ๋๋ค์ ์์ด๋์ ์ผ๊ตด์ด ์ ํ์๋ ์นด๋์ด๋ค. ๊ฐ๊ฐ์ ์นด๋์๋ ๋ฑ๊ธ์ ๋ํ๋ด๋ ์์ด ์น ํด์ ธ ์๊ณ , ๋ค์๊ณผ ๊ฐ์ด 8๊ฐ์ง๊ฐ ์๋ค.
์ ์ค์นด๋
๋ ๋์นด๋
์ค๋ ์ง์นด๋
ํผํ์นด๋
๋ธ๋ฃจ์นด๋
์ฒญ๋ก์นด๋
๊ทธ๋ฆฐ์นด๋
๊ทธ๋ ์ด์นด๋
์นด๋๋ ์นด๋ํฉ์ ํํ๋ก๋ง ๊ตฌ๋งคํ ์ ์๊ณ , ์นด๋ํฉ์ ์ข ๋ฅ๋ ์นด๋ 1๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ, ์นด๋ 2๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ, ... ์นด๋ N๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ๊ณผ ๊ฐ์ด ์ด N๊ฐ์ง๊ฐ ์กด์ฌํ๋ค.
๋ฏผ๊ท๋ ์นด๋์ ๊ฐ์๊ฐ ์ ์ ํฉ์ด๋๋ผ๋ ๊ฐ๊ฒฉ์ด ๋น์ธ๋ฉด ๋์ ๋ฑ๊ธ์ ์นด๋๊ฐ ๋ง์ด ๋ค์ด์์ ๊ฒ์ด๋ผ๋ ๋ฏธ์ ์ ๋ฏฟ๊ณ ์๋ค. ๋ฐ๋ผ์, ๋ฏผ๊ท๋ ๋์ ์ต๋ํ ๋ง์ด ์ง๋ถํด์ ์นด๋ N๊ฐ ๊ตฌ๋งคํ๋ ค๊ณ ํ๋ค. ์นด๋๊ฐ i๊ฐ ํฌํจ๋ ์นด๋ํฉ์ ๊ฐ๊ฒฉ์ Pi์์ด๋ค.
์๋ฅผ ๋ค์ด, ์นด๋ํฉ์ด ์ด 4๊ฐ์ง ์ข ๋ฅ๊ฐ ์๊ณ , P1 = 1, P2 = 5, P3 = 6, P4 = 7์ธ ๊ฒฝ์ฐ์ ๋ฏผ๊ท๊ฐ ์นด๋ 4๊ฐ๋ฅผ ๊ฐ๊ธฐ ์ํด ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต๋๊ฐ์ 10์์ด๋ค. 2๊ฐ ๋ค์ด์๋ ์นด๋ํฉ์ 2๋ฒ ์ฌ๋ฉด ๋๋ค.
P1 = 5, P2 = 2, P3 = 8, P4 = 10์ธ ๊ฒฝ์ฐ์๋ ์นด๋๊ฐ 1๊ฐ ๋ค์ด์๋ ์นด๋ํฉ์ 4๋ฒ ์ฌ๋ฉด 20์์ด๊ณ , ์ด ๊ฒฝ์ฐ๊ฐ ๋ฏผ๊ท๊ฐ ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต๋๊ฐ์ด๋ค.
๋ง์ง๋ง์ผ๋ก, P1 = 3, P2 = 5, P3 = 15, P4 = 16์ธ ๊ฒฝ์ฐ์๋ 3๊ฐ ๋ค์ด์๋ ์นด๋ํฉ๊ณผ 1๊ฐ ๋ค์ด์๋ ์นด๋ํฉ์ ๊ตฌ๋งคํด 18์์ ์ง๋ถํ๋ ๊ฒ์ด ์ต๋๊ฐ์ด๋ค.
์นด๋ ํฉ์ ๊ฐ๊ฒฉ์ด ์ฃผ์ด์ก์ ๋, N๊ฐ์ ์นด๋๋ฅผ ๊ตฌ๋งคํ๊ธฐ ์ํด ๋ฏผ๊ท๊ฐ ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. N๊ฐ๋ณด๋ค ๋ง์ ๊ฐ์์ ์นด๋๋ฅผ ์ฐ ๋ค์, ๋๋จธ์ง ์นด๋๋ฅผ ๋ฒ๋ ค์ N๊ฐ๋ฅผ ๋ง๋๋ ๊ฒ์ ๋ถ๊ฐ๋ฅํ๋ค. ์ฆ, ๊ตฌ๋งคํ ์นด๋ํฉ์ ํฌํจ๋์ด ์๋ ์นด๋ ๊ฐ์์ ํฉ์ N๊ณผ ๊ฐ์์ผ ํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฏผ๊ท๊ฐ ๊ตฌ๋งคํ๋ ค๊ณ ํ๋ ์นด๋์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. (1 โค N โค 1,000)
๋์งธ ์ค์๋ Pi๊ฐ P1๋ถํฐ PN๊น์ง ์์๋๋ก ์ฃผ์ด์ง๋ค. (1 โค Pi โค 10,000)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฏผ๊ท๊ฐ ์นด๋ N๊ฐ๋ฅผ ๊ฐ๊ธฐ ์ํด ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
๐ก 1 ~ n๊น์ง ์ซ์๋ฅผ ์ชผ๊ฐ์ dp๋ฅผ ๊ตฌ์ฑ
ex) ์ซ์ 4๋ฅผ ๊ตฌํ๋ค๋ฉด, (1+3, 2+2)๋ก ์ชผ๊ฐ์ ์๊ฐํ๊ธฐ
dp[4] = Math.max(dp[1]+dp[3], dp[2]+dp[2])
๐ก ๋ง์ง๋ง์ ๋ด๊ฐ ๊ตฌํ dp๋ ์ ๋ ฅ๋ฐ์ price ์ค ์ต๋๊ฐ ๊ณ ๋ฅด๊ธฐ
for(int i=2; i<n+1; i++) {
for(int j=1; j<=i/2; j++) {
dp[i] = Math.max(dp[i], dp[j]+dp[i-j]);
}
dp[i] = Math.max(dp[i], price[i]);
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
public class DP_17 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] price = new int[n+1];
int[] dp = new int[n+1];
String[] s = br.readLine().split(" ");
for(int i=1; i<n+1; i++) {
price[i] = Integer.parseInt(s[i-1]);
}
dp[1] = price[1];
for(int i=2; i<n+1; i++) {
for(int j=1; j<=i/2; j++) {
dp[i] = Math.max(dp[i], dp[j]+dp[i-j]);
}
dp[i] = Math.max(dp[i], price[i]);
}
bw.write(String.valueOf(dp[n]));
bw.flush();
bw.close();
}
}
์ฑ๊ณตโจ