[Algorithm] ๐Ÿšก๋ฐฑ์ค€ 2579 ๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ

0. ๋ฌธ์ œ

๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ฒŒ์ž„์€ ๊ณ„๋‹จ ์•„๋ž˜ ์‹œ์ž‘์ ๋ถ€ํ„ฐ ๊ณ„๋‹จ ๊ผญ๋Œ€๊ธฐ์— ์œ„์น˜ํ•œ ๋„์ฐฉ์ ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒŒ์ž„์ด๋‹ค. <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ™์ด ๊ฐ๊ฐ์˜ ๊ณ„๋‹จ์—๋Š” ์ผ์ •ํ•œ ์ ์ˆ˜๊ฐ€ ์“ฐ์—ฌ ์žˆ๋Š”๋ฐ ๊ณ„๋‹จ์„ ๋ฐŸ์œผ๋ฉด ๊ทธ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๋ฅผ ์–ป๊ฒŒ ๋œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด <๊ทธ๋ฆผ 2>์™€ ๊ฐ™์ด ์‹œ์ž‘์ ์—์„œ๋ถ€ํ„ฐ ์ฒซ ๋ฒˆ์งธ, ๋‘ ๋ฒˆ์งธ, ๋„ค ๋ฒˆ์งธ, ์—ฌ์„ฏ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ์•„ ๋„์ฐฉ์ ์— ๋„๋‹ฌํ•˜๋ฉด ์ด ์ ์ˆ˜๋Š” 10 + 20 + 25 + 20 = 75์ ์ด ๋œ๋‹ค.

๊ณ„๋‹จ ์˜ค๋ฅด๋Š” ๋ฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทœ์น™์ด ์žˆ๋‹ค.

1.๊ณ„๋‹จ์€ ํ•œ ๋ฒˆ์— ํ•œ ๊ณ„๋‹จ์”ฉ ๋˜๋Š” ๋‘ ๊ณ„๋‹จ์”ฉ ์˜ค๋ฅผ ์ˆ˜ ์žˆ๋‹ค. ์ฆ‰, ํ•œ ๊ณ„๋‹จ์„ ๋ฐŸ์œผ๋ฉด์„œ ์ด์–ด์„œ ๋‹ค์Œ ๊ณ„๋‹จ์ด๋‚˜, ๋‹ค์Œ ๋‹ค์Œ ๊ณ„๋‹จ์œผ๋กœ ์˜ค๋ฅผ ์ˆ˜ ์žˆ๋‹ค.
2.์—ฐ์†๋œ ์„ธ ๊ฐœ์˜ ๊ณ„๋‹จ์„ ๋ชจ๋‘ ๋ฐŸ์•„์„œ๋Š” ์•ˆ ๋œ๋‹ค. ๋‹จ, ์‹œ์ž‘์ ์€ ๊ณ„๋‹จ์— ํฌํ•จ๋˜์ง€ ์•Š๋Š”๋‹ค.
3.๋งˆ์ง€๋ง‰ ๋„์ฐฉ ๊ณ„๋‹จ์€ ๋ฐ˜๋“œ์‹œ ๋ฐŸ์•„์•ผ ํ•œ๋‹ค.

๋”ฐ๋ผ์„œ ์ฒซ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ๊ณ  ์ด์–ด ๋‘ ๋ฒˆ์งธ ๊ณ„๋‹จ์ด๋‚˜, ์„ธ ๋ฒˆ์งธ ๊ณ„๋‹จ์œผ๋กœ ์˜ค๋ฅผ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ, ์ฒซ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ๋ฐŸ๊ณ  ์ด์–ด ๋„ค ๋ฒˆ์งธ ๊ณ„๋‹จ์œผ๋กœ ์˜ฌ๋ผ๊ฐ€๊ฑฐ๋‚˜, ์ฒซ ๋ฒˆ์งธ, ๋‘ ๋ฒˆ์งธ, ์„ธ ๋ฒˆ์งธ ๊ณ„๋‹จ์„ ์—ฐ์†ํ•ด์„œ ๋ชจ๋‘ ๋ฐŸ์„ ์ˆ˜๋Š” ์—†๋‹ค.

๊ฐ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ์ด ๊ฒŒ์ž„์—์„œ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ด ์ ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ
์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์— ๊ณ„๋‹จ์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.


๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ œ์ผ ์•„๋ž˜์— ๋†“์ธ ๊ณ„๋‹จ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๊ฐ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ณ„๋‹จ์˜ ๊ฐœ์ˆ˜๋Š” 300์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๊ณ , ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๋Š” 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ฒŒ์ž„์—์„œ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ด ์ ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

3๋ฒˆ ์—ฐ์† X โ‰’ 1 or 2์นธ๋งŒ ๊ฐ„๋‹ค

2. ํ•ต์‹ฌ ํ’€์ด

  1. ํ˜„์žฌ O, ์ด์ „ O โ†’ dp[i-3]+p[i]+p[i-1]
  2. ํ˜„์žฌ 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. ๊ฒฐ๊ณผ

์„ฑ๊ณต~

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ