[๋ฐฑ์ค€] 2839 ์„คํƒ• ๋ฐฐ๋‹ฌ (feat.DP) (python ํŒŒ์ด์ฌ)

2023. 8. 20. 07:57ยท๐Ÿงฉ Problem Solving/[๋ฐฑ์ค€]
 

2839๋ฒˆ: ์„คํƒ• ๋ฐฐ๋‹ฌ

์ƒ๊ทผ์ด๋Š” ์š”์ฆ˜ ์„คํƒ•๊ณต์žฅ์—์„œ ์„คํƒ•์„ ๋ฐฐ๋‹ฌํ•˜๊ณ  ์žˆ๋‹ค. ์ƒ๊ทผ์ด๋Š” ์ง€๊ธˆ ์‚ฌํƒ•๊ฐ€๊ฒŒ์— ์„คํƒ•์„ ์ •ํ™•ํ•˜๊ฒŒ Nํ‚ฌ๋กœ๊ทธ๋žจ์„ ๋ฐฐ๋‹ฌํ•ด์•ผ ํ•œ๋‹ค. ์„คํƒ•๊ณต์žฅ์—์„œ ๋งŒ๋“œ๋Š” ์„คํƒ•์€ ๋ด‰์ง€์— ๋‹ด๊ฒจ์ ธ ์žˆ๋‹ค. ๋ด‰์ง€๋Š” 3ํ‚ฌ๋กœ๊ทธ

www.acmicpc.net


์„คํƒ• Nํ‚ฌ๋กœ๊ทธ๋žจ์„ ์ฃผ๊ณ  ์ด๊ฑธ 5ํ‚ฌ๋กœ๊ทธ๋žจ, 3ํ‚ฌ๋กœ๊ทธ๋žจ ๋ด‰์ง€๋กœ ๊ฐ€์žฅ ์ ์€ ๊ฐœ์ˆ˜๋กœ ๋‚˜๋ˆ„๋Š” ๋ฌธ์ œ. ์ฒ˜์Œ์—๋Š” ์ˆ˜ํ•™์œผ๋กœ ํ•ด๊ฒฐํ•˜๋ ค๋‹ค๊ฐ€ "๋™์ „" ๋ฌธ์ œ๊ฐ€ ์ƒ๊ฐ๋‚˜์„œ DP๋กœ ํ•ด๊ฒฐํ–ˆ๋‹ค. 


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

nํ‚ฌ๋กœ๊ทธ๋žจ์€ (n - 3) + 3 ๋˜๋Š” (n - 5) + 5๋กœ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋‹ค.

๋”ฐ๋ผ์„œ nํ‚ฌ๋กœ๊ทธ๋žจ์˜ ๋ด‰์ง€ ๊ฐœ์ˆ˜๋Š” n - 3๊ณผ n - 5 ํ‚ฌ๋กœ๊ทธ๋žจ ๋ด‰์ง€ ๊ฐœ์ˆ˜ ์ค‘ ์ž‘์€ ๊ฑฐ(min) + 1์ด ๋œ๋‹ค.

 

์ด ์•„์ด๋””์–ด๋กœ ํ•ด๊ฒฐํ•˜๋ ค๋ฉด n - 3๊ณผ n - 5์˜ ๊ฐœ์ˆ˜ ์ •๋ณด๋ฅผ ์ €์žฅํ•ด ๋’€๋‹ค๊ฐ€ ์žฌ์‚ฌ์šฉ์ด ํ•„์š”ํ•˜๋‹ค.

3 ~ nํ‚ฌ๋กœ๊ทธ๋žจ๊นŒ์ง€ ๋ด‰์ง€์˜ ์ตœ์†Œ ๊ฐœ์ˆ˜๋ฅผ ๋‹ด์„ ๋ฆฌ์ŠคํŠธ๋ฅผ ์„ ์–ธํ•ด์„œ ํ•ด๊ฒฐํ•˜๋ฉด ๋œ๋‹ค(DP).


์ „์ฒด ์ฝ”๋“œ

N = int(input())

INF = int(10e9)
DP = [INF] * (5001)

DP[3] = 1
DP[5] = 1

for i in range(6, N + 1):
        DP[i] = min(DP[i - 3], DP[i - 5]) + 1

if DP[N] < INF:
    print(DP[N])
else:
    print(-1)

์ฝ”๋“œ ์„ค๋ช…

์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์•„์ด๋””์–ด ์„ค๋ช…๊ณผ ๊ฐ™๋‹ค.

min ๋ฉ”์„œ๋“œ๋ฅผ ์“ฐ๊ธฐ ์œ„ํ•ด ๋ฆฌ์ŠคํŠธ๋ฅผ INF๊ฐ’์œผ๋กœ ์ดˆ๊ธฐํ™”ํ•ด ์ค€๋‹ค.

 

์˜ˆ๋ฅผ ๋“ค์–ด N = 10์ด๋ฉด DP[7]๊ณผ DP[5]๋ฅผ ๋น„๊ตํ•œ๋‹ค. ์ด๋•Œ ๋ด‰์ง€๋กœ 7 ํ‚ฌ๋กœ๊ทธ๋žจ์„ ๋งŒ๋“œ๋Š” ๊ฒฝ์šฐ๋Š” ์—†์œผ๋‹ˆ๊นŒ DP[7] = INF,

๋”ฐ๋ผ์„œ DP[10] = DP[5] + 1์ด ๋œ๋‹ค.

 

 

๋งˆ์ง€๋ง‰ ์ถœ๋ ฅํ•  ๋•Œ DP[N]๊ฐ’์ด INF๋ณด๋‹ค ํฌ๋ฉด -1, ์ž‘๋‹ค๋ฉด DP[N]๊ฐ’์„ ์ถœ๋ ฅํ•ด ์ค€๋‹ค.

 

 

 

 

์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'๐Ÿงฉ Problem Solving > [๋ฐฑ์ค€]' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[๋ฐฑ์ค€] 21736 ํ—Œ๋‚ด๊ธฐ๋Š” ์นœ๊ตฌ๊ฐ€ ํ•„์š”ํ•ด (python ํŒŒ์ด์ฌ)  (0) 2023.11.19
[๋ฐฑ์ค€] 18110 solved.ac (+๋ฐ˜์˜ฌ๋ฆผ ํ•จ์ˆ˜ round์— ๋Œ€ํ•ด) (python ํŒŒ์ด์ฌ)  (0) 2023.08.23
[๋ฐฑ์ค€] 2447 ๋ณ„ ์ฐ๊ธฐ - 10 (python ํŒŒ์ด์ฌ)  (0) 2023.07.30
[๋ฐฑ์ค€] 28018 ์‹œ๊ฐ„์ด ๊ฒน์น ๊นŒ?(feat.imos๋ฒ•) (python ํŒŒ์ด์ฌ)  (0) 2023.07.18
[๋ฐฑ์ค€] 28303 ์ž์„ (+ ์—ฐ์† ๊ตฌ๊ฐ„์˜ ์ตœ๋Œ€ ํ•ฉ) (python ํŒŒ์ด์ฌ)  (0) 2023.07.05
'๐Ÿงฉ Problem Solving/[๋ฐฑ์ค€]' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [๋ฐฑ์ค€] 21736 ํ—Œ๋‚ด๊ธฐ๋Š” ์นœ๊ตฌ๊ฐ€ ํ•„์š”ํ•ด (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 18110 solved.ac (+๋ฐ˜์˜ฌ๋ฆผ ํ•จ์ˆ˜ round์— ๋Œ€ํ•ด) (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 2447 ๋ณ„ ์ฐ๊ธฐ - 10 (python ํŒŒ์ด์ฌ)
  • [๋ฐฑ์ค€] 28018 ์‹œ๊ฐ„์ด ๊ฒน์น ๊นŒ?(feat.imos๋ฒ•) (python ํŒŒ์ด์ฌ)
์ œ๋ด‰์•„
์ œ๋ด‰์•„
  • ์ œ๋ด‰์•„
    Overthinking
    ์ œ๋ด‰์•„
    fake it till you make it.
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (106)
      • ๐Ÿงฉ Problem Solving (83)
        • [๋ฐฑ์ค€] (74)
        • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] (7)
        • [SW Expert Academy] (1)
        • [์•Œ๊ณ ๋ฆฌ์ฆ˜ for PS] (1)
      • ๐Ÿ“ฆ Data Structure (2)
      • ๐Ÿ“œ Language (14)
        • [python] (14)
      • ๐Ÿ–ค Git (1)
      • ๐ŸŒ† ์ผ์ƒ (4)
        • ๐Ÿ’ฌ ๋ฒฝ๋ณด๊ณ  ๋งํ•˜๊ธฐ (4)
      • ๐Ÿ—„๏ธ ๊ธฐํƒ€ (2)
      • ๐Ÿ”ต css (0)
  • ๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

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

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

  • ์ธ๊ธฐ ๊ธ€

  • ํƒœ๊ทธ

    ๋ˆ„์ ํ•ฉ
    Python
    DFS
    ์žฌ๊ท€
    ๋ฐฑํŠธ๋ž˜ํ‚น
    ๋ฐ๋ธŒ์ฝ”์Šค
    slicing
    ์œ„์ƒ์ •๋ ฌ
    boj
    ๋ธŒ๋ฃจํŠธํฌ์Šค
    ๊ตฌํ˜„
    ํ”Œ๋กœ์ด๋“œ์›Œ์…œ
    ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
    ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ
    ์Šคํƒ
    Bruteforce
    ํŒฐ๋ฆฐ๋“œ๋กฌ
    BFS
    ๋ถ€๋ถ„ํ•ฉ
    ๋ฐฑ์ค€
    imos
    SWEA
    ๊ทธ๋ฆฌ๋””
    ๋‹ค์ต์ŠคํŠธ๋ผ
    ํˆฌํฌ์ธํ„ฐ
    ์ •์ฒ˜๊ธฐ
    ๋ƒ…์ƒ‰
    ๋ถ„ํ•  ์ •๋ณต
    DP
    ํŒŒ์ด์ฌ
  • ์ตœ๊ทผ ๋Œ“๊ธ€

  • ์ตœ๊ทผ ๊ธ€

  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
์ œ๋ด‰์•„
[๋ฐฑ์ค€] 2839 ์„คํƒ• ๋ฐฐ๋‹ฌ (feat.DP) (python ํŒŒ์ด์ฌ)
์ƒ๋‹จ์œผ๋กœ

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