๋ฐฑ์ค€์˜จ๋ผ์ธ์ €์ง€ 2759 ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ์ž๋ฐ”ํ’€์ด

2020. 7. 12. 15:07ยท ์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ณธ ๋ฌธ์ œ๋Š” ๋™์ ๊ณ„ํš๋ฒ•(DynamicPrograming)์„ ์ด์šฉํ•˜์—ฌ ํ’€์–ด์•ผ ํ•œ๋‹ค. ๋ณต์žกํ•œ ๋ฌธ์ œ๋ฅผ ๊ฐ„๋‹จํ•œ ์—ฌ๋Ÿฌ๊ฐœ๋กœ ๋‚˜๋ˆ„์–ด์„œ ํ•ด๊ฒฐํ•˜๋Š” ๊ธฐ๋ฒ•์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฐ ์ด์œ ๋กœ ํŒจํ„ด(๊ทœ์น™)์„ ์ฐพ์•„ ๋ฐฐ์—ด์•ˆ์— ์ดˆ๊ธฐ๊ฐ’์„ ํ• ๋‹นํ•˜๊ณ , for๋ฌธ์„ ๋Œ๋ฆฌ๋Š” bottom-up ๋ฐฉ์‹์ด๋‚˜ ์žฌ๊ท€๋ฅผ ์ด์šฉํ•˜๋Š” top-down ๋ฐฉ์‹์ด ์žˆ์Šต๋‹ˆ๋‹ค. 

 

https://www.acmicpc.net/problem/2579

 

2579๋ฒˆ: ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ

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

www.acmicpc.net

์ €๋Š” bottom-up์œผ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด์„ ์šฉ๋„๋กœ ๋ฐฐ์—ด์„ ์„ ํƒํ–ˆ์Šต๋‹ˆ๋‹ค. ์‚ฌ์šฉ์ž์˜ ์ž…๋ ฅํฌ๊ธฐ ๋งŒํผ์˜ ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜๊ณ , ์ดˆ๊ธฐ๊ฐ’์„ ๋„ฃ์—ˆ์Šต๋‹ˆ๋‹ค.

 

์ดํ›„์— ๊ณ ๋ฏผ์„ ํ–ˆ๋˜๊ฒŒ for๋ฌธ์„ ํ†ตํ•ด ๊ฐ’์„ ๋”ํ•ด๋‚˜๊ฐ€์•ผ ํ•˜๋Š”๋ฐ ๊ทธ ๋ถ€๋ถ„์„ ์–ด๋–ป๊ฒŒ ๊ตฌ์ƒํ•˜๋ƒ๋Š” ๊ฒƒ์ด์˜€์Šต๋‹ˆ๋‹ค. ๊ฐ€๋ น, dp[4] ์ฆ‰ ๊ณ„๋‹จ 4๊นŒ์ง€์˜ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•œ๋‹ค๋ฉด ๊ณ„๋‹จ ๋ณ„๋กœ 1, 2, 4 ํ˜น์€ 1, 3, 4๋ฅผ ๋น„๊ตํ•ด์•ผ ํ•  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ผ๋ฐ˜์ ์ธ ๊ฒฝ์šฐ๋Š” n>=3 ์ด์ƒ์ผ ๋•Œ ์ด๋ฏ€๋กœ for๋ฌธ์˜ ์ดˆ๊ธฐ๊ฐ’์€ 3์ด๋ฉด ๋์Šต๋‹ˆ๋‹ค. 

 

์ œ๊ฐ€ ์ด ๋ถ€๋ถ„์„ ์ œ๋Œ€๋กœ ํ•˜์ง€ ๋ชปํ–ˆ๋˜ ์ด์œ ๋Š” dp[] ๋ผ๋Š” ํ•˜๋‚˜์˜ ๋ฐฐ์—ด์— ๋ˆ„์ ์œผ๋กœ ๋”ํ•ด๋‚˜๊ฐ€๋ ค๊ณ  ํ•œ ๊ฒƒ์— ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ณ„๋‹จ ๋ฌธ์ œ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ์—ฐ์† 3๊ฐœ์˜ ๊ณ„๋‹จ์€ ๋ฐŸ์ง€ ๋ชปํ•œ๋‹ค ๋ผ๋Š” ์กฐ๊ฑด์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๋Ÿฐ์‹์œผ๋กœ ์ฝ”๋”ฉ์„ ํ•˜๋ฉด ๋ฐฉ๋ฒ•์ด ์—†์—ˆ์Šต๋‹ˆ๋‹ค. 

 

๋”ฐ๋ผ์„œ ๋ฐฐ์—ด์„ 2๊ฐœ ๊ตฌ์„ฑํ•ด์•ผ ํ–ˆ์Šต๋‹ˆ๋‹ค. ํ•˜๋‚˜์˜ ๋ฐฐ์—ด์€ ๋ˆ„์ ๊ฐ’, ํ•˜๋‚˜์˜ ๋ฐฐ์—ด์€ ๊ณ„๋‹จ์˜ ์ ์ˆ˜๊ฐ€ ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์ €์„ธ์ƒ ๊ทธ๋ฆผ ใ…ˆใ……

์—ฐ์†๋œ 3๊ณ„๋‹จ์„ ๋ฐŸ์ง€ ๋ชปํ•œ๋‹ค๋ฉด 2๊ฐ€์ง€์˜ ๊ฒฝ์šฐ๋ฅผ ๊ณ ๋ คํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. 2์นธ ์˜ฌ๋ž์„ ๋•Œ, ๋ชฉ์ ์ง€์ธ ๊ฒฝ์šฐ์™€ 1์นธ ์˜ฌ๋ž์„ ๋•Œ, ๋ชฉ์ ์ง€์ธ ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค. 1๋ฒˆ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ๋ฐ”๋กœ ๋‹น์—ฐํžˆ ์˜ฌ๋ผ๊ฐ€๊ธฐ ์ „ ๊ณ„๋‹จ์—์„œ 2์นธ ๋–จ์–ด์ง„ ๊ณ„๋‹จ์˜ ๋ˆ„์ ์ ์ˆ˜+ํ˜„์žฌ๊ณ„๋‹จ+๋ชฉ์ ์ง€ ์ ์ˆ˜๋ฅผ ํ•ฉํ•ด์•ผํ•˜๊ณ , 2๋ฒˆ ๊ฐ™์€ ๊ฒฝ์šฐ๋Š” ์˜ฌ๋ผ๊ฐ€๊ธฐ ์ „ ๊ณ„๋‹จ์˜ ๋ˆ„์ ํ•ฉ๊ณผ ๋ชฉ์ ์ง€์˜ ์ ์ˆ˜๋ฅผ ํ•ฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. 

 

๊ณ„๋‹จ 1๊ณผ ๊ณ„๋‹จ 2๋Š” ๋ฐฐ์—ด์˜ ๊ฐ’์„ ๋„ฃ๊ณ , for๋ฌธ์„ ์ด์šฉํ•ฉ๋‹ˆ๋‹ค.

package dynamicPrograming6;

import java.io.*;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static int dp[];
	static int stairs[];
	static int n;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		
		stairs = new int[n+1];
		dp = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			stairs[i] = Integer.parseInt(br.readLine());
		}
		
		dp[1] = stairs[1];
		
		if(n>=2) { //์ดˆ๋ฐ˜ ์˜ค๋ฅ˜ ๋ฐฉ์ง€
			dp[2] = stairs[1] + stairs[2]; // ๊ณ„๋‹จ 2์˜ ๋ˆ„์ ํ•ฉ
		}
		for(int i=3; i<=n; i++) {
			dp[i] = Math.max(stairs[i] + dp[i-2], stairs[i-1]+ stairs[i] + dp[i-3]); //dp๋Š” ๋ˆ„์ ํ•ฉ, stairs๋Š” ๊ณ„๋‹จ์˜ ์ ์ˆ˜
		}
		
		bw.write(String.valueOf(dp[n])+"\n");
		bw.flush();
		
		br.close();
		bw.close();
	}

}

'์•Œ๊ณ ๋ฆฌ์ฆ˜' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

ํฐ ์ˆ˜์˜ ๋ง์…ˆ  (0) 2021.06.09
[์•Œ๊ณ ๋ฆฌ์ฆ˜] DFS, BFS์˜ ๊ตฌํ˜„  (0) 2020.10.13
10816 ์ˆซ์ž ์นด๋“œ 2  (0) 2020.08.05
1051๋ฒˆ: ์ˆซ์ž ์ •์‚ฌ๊ฐํ˜•  (0) 2020.08.05
๋ฐฑ์ค€ 1012 ์œ ๊ธฐ๋† ๋ฐฐ์ถ” (์ž๋ฐ”)  (0) 2020.07.27
'์•Œ๊ณ ๋ฆฌ์ฆ˜' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [์•Œ๊ณ ๋ฆฌ์ฆ˜] DFS, BFS์˜ ๊ตฌํ˜„
  • 10816 ์ˆซ์ž ์นด๋“œ 2
  • 1051๋ฒˆ: ์ˆซ์ž ์ •์‚ฌ๊ฐํ˜•
  • ๋ฐฑ์ค€ 1012 ์œ ๊ธฐ๋† ๋ฐฐ์ถ” (์ž๋ฐ”)
๊น€ํƒœ์ง„
๊น€ํƒœ์ง„
์„ฑ์žฅํ•˜๊ธฐ ์œ„ํ•œ ๊ธ€์„ ์ž‘์„ฑํ•˜๋ ค๊ณ  ๋…ธ๋ ฅ์ค‘ ์ž…๋‹ˆ๋‹ค
๊น€ํƒœ์ง„
My Dev History๐Ÿ’ป
๊น€ํƒœ์ง„
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (131)
    • ํŒŒ์ด์ฌ (8)
    • ์•Œ๊ณ ๋ฆฌ์ฆ˜ (24)
    • ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ (13)
      • ํ”„๋กœ์ ํŠธ (6)
      • ์ด๋ก  (6)
    • html&css (3)
    • css (6)
    • TIL (6)
    • react (15)
    • ํšŒ๊ณ  (5)
      • ์ฃผ๊ฐ„ํšŒ๊ณ  (2)
    • ๊ฐ•์˜ ์ •๋ฆฌ (3)
      • ์ฝ”๋“œ์ž‡ ๋ฆฌ์•กํŠธ ๊ฐ•์˜ ๋ชจ์Œ (3)
    • ์˜ค๋ฅ˜๋กœ๊ทธ (4)
    • ํ”„๋กœ์ ํŠธ (15)
    • ํƒ€์ž…์Šคํฌ๋ฆฝํŠธ (2)
    • Computer Science (4)
      • ๋จธ์‹ ๋Ÿฌ๋‹ (3)
      • ์ปดํ“จํ„ฐ๋„คํŠธ์›Œํฌ (1)
    • ์˜คํ”ˆ์†Œ์Šค (3)
    • ์›น (1)
    • ์ฝ”๋“œ๊ฐœ์„  (1)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • Object
  • css property
  • CSS
  • Flappy game
  • Recoil
  • ๊ฒŒ์ž„
  • white-space
  • ์ƒ์†
  • ๊ฐœ๋ฐœ์ž
  • react
  • ๋ฆฌ์•กํŠธ
  • ์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ
  • prototype
  • canvas api
  • react icons
  • ํ”„๋ก ํŠธ์—”๋“œ
  • game
  • redux
  • ๊ณต์‹๋ฌธ์„œ
  • ์˜คํ”ˆ์†Œ์Šค
  • initial value
  • ์˜คํ”ˆ์†Œ์Šค ๊ธฐ์—ฌ
  • javascript

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.v4.2.2
๊น€ํƒœ์ง„
๋ฐฑ์ค€์˜จ๋ผ์ธ์ €์ง€ 2759 ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ์ž๋ฐ”ํ’€์ด
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.