์ƒˆ์†Œ์‹

๐Ÿงฎ ์•Œ๊ณ ๋ฆฌ์ฆ˜/-- ๋ฐฑ์ค€ (BOJ) - Python

๋ฐฑ์ค€ (boj) ํŒŒ์ด์ฌ - 11726 ๋ฒˆ : 2 x n ํƒ€์ผ๋ง (DP)

  • -

๋ฌธ์ œ ๋งํฌ : https://www.acmicpc.net/problem/11726

 

11726๋ฒˆ: 2×n ํƒ€์ผ๋ง

2×n ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์„ 1×2, 2×1 ํƒ€์ผ๋กœ ์ฑ„์šฐ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์•„๋ž˜ ๊ทธ๋ฆผ์€ 2×5 ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์„ ์ฑ„์šด ํ•œ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์˜ ์˜ˆ์ด๋‹ค.

www.acmicpc.net

 

 

 


 

 

๋ฌธ์ œ ๋ถ„๋ฅ˜ : ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ https://infinitt.tistory.com/246

 

์•Œ๊ณ ๋ฆฌ์ฆ˜ - ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ (Dynamic Programming)

๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ (Dynamic Programming) : DP ๊ฐœ๋… : ๋ฌธ์ œ๋ฅผ ๋” ์ž‘์€ ๋‹จ์œ„๋กœ ์ชผ๊ฐœ์–ด ํ•ด๊ฒฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜. (๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋น„์Šทํ•˜๋‹ค. ์ฐจ์ด์ ์€ ๋ฐ”๋กœ ์•„๋žซ์ค„.) ํ•ต์‹ฌ์€, ๊ทธ ์ž‘์€ ๋‹จ์œ„์˜ ๋ฌธ์ œ๋“ค์ด ๋ฐ˜๋ณตํ•ด์„œ..

infinitt.tistory.com

 

 

์ƒ๊ฐ๋ณด๋‹ค ์ ํ™”์‹์ด ๋นจ๋ฆฌ ์ฐพ์•„์กŒ๋‹ค. ๋ฌธ์ œ์˜ ์˜๋„๋Š” ํƒ€์ผ์˜ ๊ตฌ์„ฑ์„ ํ†ตํ•ด ์ ํ™”์‹์„ ์ฐพ์œผ๋ผ๋Š”๊ฒƒ ๊ฐ™์€๋ฐ ์ˆซ์ž๋ฅผ ๋ณด๋ฉด ํ”ผ๋ณด๋‚˜์น˜์™€ ์œ ์‚ฌํ•œ ํ˜•ํƒœ์˜ ์ ํ™”์‹์ด ์„ธ์›Œ์ง„๋‹ค.

 ์ž…๋ ฅ N 1 2 3 4 5 6
 ๋ฐฉ๋ฒ•์˜ ์ˆ˜ 1 2 3 5 8 13

 

์ ํ™”์‹ : dp[N] = dp[N-1]+dp[N-2]

 

 

 

 

 

 

*์ •๋‹ต์ฝ”๋“œ (Python)
n = int(input())

dp = [0 for _ in range(n+1)]

if n <= 3 : print(n)
else : 
	dp[1] = 1
	dp[2] = 2
	for i in range(3, n+1):
		dp[i] = dp[i-1] + dp[i-2]

	print(dp[i]%10007)
		

 

Contents

ํฌ์ŠคํŒ… ์ฃผ์†Œ๋ฅผ ๋ณต์‚ฌํ–ˆ์Šต๋‹ˆ๋‹ค

์ด ๊ธ€์ด ๋„์›€์ด ๋˜์—ˆ๋‹ค๋ฉด ๊ณต๊ฐ ๋ถ€ํƒ๋“œ๋ฆฝ๋‹ˆ๋‹ค.