deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

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

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

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

์ธ๊ธฐ ๊ธ€

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

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim

๋งž์™œํ‹€

[python] ๋ฐฑ์ค€ - 2133. ํƒ€์ผ ์ฑ„์šฐ๊ธฐ
Algorithm Problem/Python

[python] ๋ฐฑ์ค€ - 2133. ํƒ€์ผ ์ฑ„์šฐ๊ธฐ

2020. 10. 7. 10:50
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

  • S2 | DP

์ด๋Ÿฐ๋ฌธ์ œ๋Š” ์—ญ์‹œ ๋‹จ๊ณจ DP๋ฌธ์ œ

์ผ๋‹จ ์†์œผ๋กœ ๊ตฌํ•ด๋ดค๋‹ค.

          i == 0, 2, 4, 6 ( ํ™€์ˆ˜ ์ผ ๊ฒฝ์šฐ๋Š” ์ œ์™ธํ•จ )

๊ฒฝ์šฐ์˜์ˆ˜ == 1, 3, 11, 41

 

์ ํ™”์‹

dp[i] = dp[i-2] * 3 + (dp[2] ~ dp[i-2]) * 2 + 2

i๊ฒฝ์šฐ์˜์ˆ˜ = ์ด์ „์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜ * 3 + ์ด์ „์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜ ๋“ค * 2 + i๋งŒ ๋งŒ๋“œ๋Š” ๊ฒฝ์šฐ

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

N = int(input())
if N % 2:
    print(0)

else:
    dp = [0] * (N + 1)
    dp[0], dp[2] = 1, 3

    for i in range(4, N + 1, 2):
        dp[i] = dp[i - 2] * 3 + 2
        for j in range(2, i - 2, 2):
            dp[i] += dp[j] * 2

    print(dp[N])
 

 

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: BACKJOON ONLINE JUDGE

๋งํฌ: https://www.acmicpc.net/problem/2133

 

2133๋ฒˆ: ํƒ€์ผ ์ฑ„์šฐ๊ธฐ

3×N ํฌ๊ธฐ์˜ ๋ฒฝ์„ 2×1, 1×2 ํฌ๊ธฐ์˜ ํƒ€์ผ๋กœ ์ฑ„์šฐ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด๋ณด์ž.

www.acmicpc.net

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Algorithm Problem > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[python] ๋ฐฑ์ค€ - 10819. ์ฐจ์ด๋ฅผ ์ตœ๋Œ€๋กœ  (0) 2020.10.09
[python] ๋ฐฑ์ค€ - 1541. ์žƒ์–ด๋ฒ„๋ฆฐ ๊ด„ํ˜ธ  (0) 2020.10.08
[python] ๋ฐฑ์ค€ - 11729. ํ•˜๋…ธ์ด ํƒ‘ ์ด๋™ ์ˆœ์„œ  (0) 2020.10.06
[python] ๋ฐฑ์ค€ - 1182. ๋ถ€๋ถ„์ˆ˜์—ด์˜ ํ•ฉ  (0) 2020.10.05
[python] ๋ฐฑ์ค€ - 11055. ๊ฐ€์žฅ ํฐ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด  (0) 2020.10.04
    'Algorithm Problem/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [python] ๋ฐฑ์ค€ - 10819. ์ฐจ์ด๋ฅผ ์ตœ๋Œ€๋กœ
    • [python] ๋ฐฑ์ค€ - 1541. ์žƒ์–ด๋ฒ„๋ฆฐ ๊ด„ํ˜ธ
    • [python] ๋ฐฑ์ค€ - 11729. ํ•˜๋…ธ์ด ํƒ‘ ์ด๋™ ์ˆœ์„œ
    • [python] ๋ฐฑ์ค€ - 1182. ๋ถ€๋ถ„์ˆ˜์—ด์˜ ํ•ฉ
    deo2kim
    deo2kim
    ์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

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