[Algorithm] ๐ก๋ฐฑ์ค 2579 ๊ณ๋จ์ค๋ฅด๊ธฐ
0. ๋ฌธ์
๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ฒ์์ ๊ณ๋จ ์๋ ์์์ ๋ถํฐ ๊ณ๋จ ๊ผญ๋๊ธฐ์ ์์นํ ๋์ฐฉ์ ๊น์ง ๊ฐ๋ ๊ฒ์์ด๋ค. <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ๊ฐ๊ฐ์ ๊ณ๋จ์๋ ์ผ์ ํ ์ ์๊ฐ ์ฐ์ฌ ์๋๋ฐ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด ๊ทธ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๋ฅผ ์ป๊ฒ ๋๋ค.
์๋ฅผ ๋ค์ด <๊ทธ๋ฆผ 2>์ ๊ฐ์ด ์์์ ์์๋ถํฐ ์ฒซ ๋ฒ์งธ, ๋ ๋ฒ์งธ, ๋ค ๋ฒ์งธ, ์ฌ์ฏ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ์ ๋์ฐฉ์ ์ ๋๋ฌํ๋ฉด ์ด ์ ์๋ 10 + 20 + 25 + 20 = 75์ ์ด ๋๋ค.
๊ณ๋จ ์ค๋ฅด๋ ๋ฐ๋ ๋ค์๊ณผ ๊ฐ์ ๊ท์น์ด ์๋ค.
1.๊ณ๋จ์ ํ ๋ฒ์ ํ ๊ณ๋จ์ฉ ๋๋ ๋ ๊ณ๋จ์ฉ ์ค๋ฅผ ์ ์๋ค. ์ฆ, ํ ๊ณ๋จ์ ๋ฐ์ผ๋ฉด์ ์ด์ด์ ๋ค์ ๊ณ๋จ์ด๋, ๋ค์ ๋ค์ ๊ณ๋จ์ผ๋ก ์ค๋ฅผ ์ ์๋ค.
2.์ฐ์๋ ์ธ ๊ฐ์ ๊ณ๋จ์ ๋ชจ๋ ๋ฐ์์๋ ์ ๋๋ค. ๋จ, ์์์ ์ ๊ณ๋จ์ ํฌํจ๋์ง ์๋๋ค.
3.๋ง์ง๋ง ๋์ฐฉ ๊ณ๋จ์ ๋ฐ๋์ ๋ฐ์์ผ ํ๋ค.
๋ฐ๋ผ์ ์ฒซ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ณ ์ด์ด ๋ ๋ฒ์งธ ๊ณ๋จ์ด๋, ์ธ ๋ฒ์งธ ๊ณ๋จ์ผ๋ก ์ค๋ฅผ ์ ์๋ค. ํ์ง๋ง, ์ฒซ ๋ฒ์งธ ๊ณ๋จ์ ๋ฐ๊ณ ์ด์ด ๋ค ๋ฒ์งธ ๊ณ๋จ์ผ๋ก ์ฌ๋ผ๊ฐ๊ฑฐ๋, ์ฒซ ๋ฒ์งธ, ๋ ๋ฒ์งธ, ์ธ ๋ฒ์งธ ๊ณ๋จ์ ์ฐ์ํด์ ๋ชจ๋ ๋ฐ์ ์๋ ์๋ค.
๊ฐ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๊ฐ ์ฃผ์ด์ง ๋ ์ด ๊ฒ์์์ ์ป์ ์ ์๋ ์ด ์ ์์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ ๋ ฅ์ ์ฒซ์งธ ์ค์ ๊ณ๋จ์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ ํ ์ค์ ํ๋์ฉ ์ ์ผ ์๋์ ๋์ธ ๊ณ๋จ๋ถํฐ ์์๋๋ก ๊ฐ ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ณ๋จ์ ๊ฐ์๋ 300์ดํ์ ์์ฐ์์ด๊ณ , ๊ณ๋จ์ ์ฐ์ฌ ์๋ ์ ์๋ 10,000์ดํ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ณ๋จ ์ค๋ฅด๊ธฐ ๊ฒ์์์ ์ป์ ์ ์๋ ์ด ์ ์์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
1. ์์ด๋์ด
3๋ฒ ์ฐ์ X โ 1 or 2์นธ๋ง ๊ฐ๋ค
2. ํต์ฌ ํ์ด
- ํ์ฌ O, ์ด์ O โ dp[i-3]+p[i]+p[i-1]
- ํ์ฌ O, ์ด์ X โ dp[i-2] + p[i]
dp[i] = Math.max(dp[i-3]+score[i]+score[i-1], dp[i-2]+score[i]);
3. ์ฝ๋
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]);
}
}
4. ๊ฒฐ๊ณผ
์ฑ๊ณต~
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐ก๋ฐฑ์ค 2579 ๊ณ๋จ์ค๋ฅด๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๋ฐฑ์ค-2579-๊ณ๋จ์ค๋ฅด๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค