J1Yun
ZU-TECHLOG
J1Yun
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๐Ÿ“‘ Category (135)
    • Algorithm (61)
      • ๐Ÿ“š Concept (6)
      • ๐Ÿ“˜ Baekjoon Judge (53)
      • ๐Ÿ“— Programmers (2)
    • Computer Science (42)
      • ๐Ÿ”’ Operating System (14)
      • ๐Ÿ“ก Network (15)
      • ๐Ÿ’พ Database (8)
      • ๐Ÿงฉ Design Pattern (4)
      • ๐Ÿ”‘ Security (1)
    • Activities (12)
      • ๐Ÿฆ ๋ฉ‹์Ÿ์ด์‚ฌ์ž์ฒ˜๋Ÿผ 9๊ธฐ (6)
      • ๐Ÿ’ป SW๋งˆ์—์ŠคํŠธ๋กœ 13๊ธฐ (6)
    • Infra (1)
      • โ˜๏ธ AWS (1)
    • Languages (1)
      • ๐Ÿ’™ Python (1)
    • Backend (7)
      • ๐Ÿ”ต Django (4)
      • ๐ŸŸข Node.js (3)
    • Ect. (8)
      • ๐Ÿ’ฌ Talk (0)
      • ๐Ÿ—‚๏ธ ๊ฐœ๋ฐœ์ง๊ตฐ ์ทจ์—… ์ค€๋น„์ž๋ฃŒ (8)

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

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

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

์ธ๊ธฐ ๊ธ€

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

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

250x250
hELLO ยท Designed By ์ •์ƒ์šฐ.
J1Yun

ZU-TECHLOG

[BOJ] ๋ฐฑ์ค€ 11052๋ฒˆ ์นด๋“œ ๊ตฌ๋งคํ•˜๊ธฐ - ํŒŒ์ด์ฌ(Python)
Algorithm/๐Ÿ“˜ Baekjoon Judge

[BOJ] ๋ฐฑ์ค€ 11052๋ฒˆ ์นด๋“œ ๊ตฌ๋งคํ•˜๊ธฐ - ํŒŒ์ด์ฌ(Python)

728x90

๋ฌธ์ œ

์š”์ฆ˜ ๋ฏผ๊ทœ๋„ค ๋™๋„ค์—์„œ๋Š” ์Šคํƒ€ํŠธ๋งํฌ์—์„œ ๋งŒ๋“  PS์นด๋“œ๋ฅผ ๋ชจ์œผ๋Š” ๊ฒƒ์ด ์œ ํ–‰์ด๋‹ค.

PS์นด๋“œ๋Š” PS(Problem Solving)๋ถ„์•ผ์—์„œ ์œ ๋ช…ํ•œ ์‚ฌ๋žŒ๋“ค์˜ ์•„์ด๋””์™€ ์–ผ๊ตด์ด ์ ํ˜€์žˆ๋Š” ์นด๋“œ์ด๋‹ค. ๊ฐ๊ฐ์˜ ์นด๋“œ์—๋Š” ๋“ฑ๊ธ‰์„ ๋‚˜ํƒ€๋‚ด๋Š” ์ƒ‰์ด ์น ํ•ด์ ธ ์žˆ๊ณ , ๋‹ค์Œ๊ณผ ๊ฐ™์ด 8๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.

  • ์ „์„ค์นด๋“œ
  • ๋ ˆ๋“œ์นด๋“œ
  • ์˜ค๋ Œ์ง€์นด๋“œ
  • ํผํ”Œ์นด๋“œ
  • ๋ธ”๋ฃจ์นด๋“œ
  • ์ฒญ๋ก์นด๋“œ
  • ๊ทธ๋ฆฐ์นด๋“œ
  • ๊ทธ๋ ˆ์ด์นด๋“œ

์นด๋“œ๋Š” ์นด๋“œํŒฉ์˜ ํ˜•ํƒœ๋กœ๋งŒ ๊ตฌ๋งคํ•  ์ˆ˜ ์žˆ๊ณ , ์นด๋“œํŒฉ์˜ ์ข…๋ฅ˜๋Š” ์นด๋“œ 1๊ฐœ๊ฐ€ ํฌํ•จ๋œ ์นด๋“œํŒฉ, ์นด๋“œ 2๊ฐœ๊ฐ€ ํฌํ•จ๋œ ์นด๋“œํŒฉ, ... ์นด๋“œ N๊ฐœ๊ฐ€ ํฌํ•จ๋œ ์นด๋“œํŒฉ๊ณผ ๊ฐ™์ด ์ด N๊ฐ€์ง€๊ฐ€ ์กด์žฌํ•œ๋‹ค.

๋ฏผ๊ทœ๋Š” ์นด๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ ์€ ํŒฉ์ด๋”๋ผ๋„ ๊ฐ€๊ฒฉ์ด ๋น„์‹ธ๋ฉด ๋†’์€ ๋“ฑ๊ธ‰์˜ ์นด๋“œ๊ฐ€ ๋งŽ์ด ๋“ค์–ด์žˆ์„ ๊ฒƒ์ด๋ผ๋Š” ๋ฏธ์‹ ์„ ๋ฏฟ๊ณ  ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ, ๋ฏผ๊ทœ๋Š” ๋ˆ์„ ์ตœ๋Œ€ํ•œ ๋งŽ์ด ์ง€๋ถˆํ•ด์„œ ์นด๋“œ N๊ฐœ ๊ตฌ๋งคํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์นด๋“œ๊ฐ€ i๊ฐœ ํฌํ•จ๋œ ์นด๋“œํŒฉ์˜ ๊ฐ€๊ฒฉ์€ Pi์›์ด๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์นด๋“œํŒฉ์ด ์ด 4๊ฐ€์ง€ ์ข…๋ฅ˜๊ฐ€ ์žˆ๊ณ , P1 = 1, P2 = 5, P3 = 6, P4 = 7์ธ ๊ฒฝ์šฐ์— ๋ฏผ๊ทœ๊ฐ€ ์นด๋“œ 4๊ฐœ๋ฅผ ๊ฐ–๊ธฐ ์œ„ํ•ด ์ง€๋ถˆํ•ด์•ผ ํ•˜๋Š” ๊ธˆ์•ก์˜ ์ตœ๋Œ“๊ฐ’์€ 10์›์ด๋‹ค. 2๊ฐœ ๋“ค์–ด์žˆ๋Š” ์นด๋“œํŒฉ์„ 2๋ฒˆ ์‚ฌ๋ฉด ๋œ๋‹ค.

P1 = 5, P2 = 2, P3 = 8, P4 = 10์ธ ๊ฒฝ์šฐ์—๋Š” ์นด๋“œ๊ฐ€ 1๊ฐœ ๋“ค์–ด์žˆ๋Š” ์นด๋“œํŒฉ์„ 4๋ฒˆ ์‚ฌ๋ฉด 20์›์ด๊ณ , ์ด ๊ฒฝ์šฐ๊ฐ€ ๋ฏผ๊ทœ๊ฐ€ ์ง€๋ถˆํ•ด์•ผ ํ•˜๋Š” ๊ธˆ์•ก์˜ ์ตœ๋Œ“๊ฐ’์ด๋‹ค.

๋งˆ์ง€๋ง‰์œผ๋กœ, P1 = 3, P2 = 5, P3 = 15, P4 = 16์ธ ๊ฒฝ์šฐ์—๋Š” 3๊ฐœ ๋“ค์–ด์žˆ๋Š” ์นด๋“œํŒฉ๊ณผ 1๊ฐœ ๋“ค์–ด์žˆ๋Š” ์นด๋“œํŒฉ์„ ๊ตฌ๋งคํ•ด 18์›์„ ์ง€๋ถˆํ•˜๋Š” ๊ฒƒ์ด ์ตœ๋Œ“๊ฐ’์ด๋‹ค.

์นด๋“œ ํŒฉ์˜ ๊ฐ€๊ฒฉ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, N๊ฐœ์˜ ์นด๋“œ๋ฅผ ๊ตฌ๋งคํ•˜๊ธฐ ์œ„ํ•ด ๋ฏผ๊ทœ๊ฐ€ ์ง€๋ถˆํ•ด์•ผ ํ•˜๋Š” ๊ธˆ์•ก์˜ ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. N๊ฐœ๋ณด๋‹ค ๋งŽ์€ ๊ฐœ์ˆ˜์˜ ์นด๋“œ๋ฅผ ์‚ฐ ๋‹ค์Œ, ๋‚˜๋จธ์ง€ ์นด๋“œ๋ฅผ ๋ฒ„๋ ค์„œ N๊ฐœ๋ฅผ ๋งŒ๋“œ๋Š” ๊ฒƒ์€ ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค. ์ฆ‰, ๊ตฌ๋งคํ•œ ์นด๋“œํŒฉ์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ์นด๋“œ ๊ฐœ์ˆ˜์˜ ํ•ฉ์€ N๊ณผ ๊ฐ™์•„์•ผ ํ•œ๋‹ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ๋ฏผ๊ทœ๊ฐ€ ๊ตฌ๋งคํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นด๋“œ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000)

๋‘˜์งธ ์ค„์—๋Š” Pi๊ฐ€ P1๋ถ€ํ„ฐ PN๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Pi ≤ 10,000)

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๋ฏผ๊ทœ๊ฐ€ ์นด๋“œ N๊ฐœ๋ฅผ ๊ฐ–๊ธฐ ์œ„ํ•ด ์ง€๋ถˆํ•ด์•ผ ํ•˜๋Š” ๊ธˆ์•ก์˜ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

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

 

11052๋ฒˆ: ์นด๋“œ ๊ตฌ๋งคํ•˜๊ธฐ

์ฒซ์งธ ์ค„์— ๋ฏผ๊ทœ๊ฐ€ ๊ตฌ๋งคํ•˜๋ ค๊ณ  ํ•˜๋Š” ์นด๋“œ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000) ๋‘˜์งธ ์ค„์—๋Š” Pi๊ฐ€ P1๋ถ€ํ„ฐ PN๊นŒ์ง€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

 

๐Ÿ’ก ํ’€์ด ๋ฐ ์ฝ”๋“œ

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))

d = [0] * (n+1)
d[1] = data[0]
for i in range(2,n+1):
    d[i] = data[i-1]
    for j in range(1,i//2+1):
        d[i] = max(d[i], d[i-j]+data[j-1])


print(d[n])

๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์œผ๋กœ ์‰ฝ๊ฒŒ ํ’€์ดํ•  ์ˆ˜ ์žˆ๋‹ค.

i๊ฐœ์˜ ์นด๋“œ๋ฅผ ๊ตฌ๋งคํ•˜๋ ค๊ณ  ํ•œ๋‹ค๋ฉด 1๋ถ€ํ„ฐ i//2๊นŒ์ง€ ์ฆ๊ฐ€ํ•˜๋Š” j๋ฅผ ๋‘์–ด iํŒฉ์˜ ๊ธˆ์•ก(data[i-1])๊ณผ DP ํ…Œ์ด๋ธ”์— ์ €์žฅ๋œ i-jํŒฉ๊นŒ์ง€์˜ ์ตœ๋Œ€ ๊ธˆ์•ก(d[i-j])์— jํŒฉ์˜ ๊ธˆ์•ก(data[j-1])์„ ๋”ํ•œ ๊ฐ’๋“ค ์ค‘ ์ตœ๋Œ€๋ฅผ ๊ตฌํ•ด DPํ…Œ์ด๋ธ” d[i]์—๋‹ค ๊ฐฑ์‹ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค. j๋ฅผ i//2๊นŒ์ง€๋งŒ ์ฆ๊ฐ€์‹œํ‚ค๋Š” ์ด์œ ๋Š” 1ํŒฉ+3ํŒฉ๊ณผ 3ํŒฉ+1ํŒฉ์„ ๊ตฌ๋ถ„ํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

728x90

'Algorithm > ๐Ÿ“˜ Baekjoon Judge' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[BOJ] ๋ฐฑ์ค€ 1012๋ฒˆ ์œ ๊ธฐ๋† ๋ฐฐ์ถ” - ํŒŒ์ด์ฌ(Python)  (0) 2021.10.07
[BOJ] ๋ฐฑ์ค€ 14501๋ฒˆ ํ‡ด์‚ฌ - ํŒŒ์ด์ฌ(Python)  (0) 2021.10.06
[BOJ] ๋ฐฑ์ค€ 10844๋ฒˆ ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜ - ํŒŒ์ด์ฌ(Python)  (0) 2021.09.15
[BOJ] ๋ฐฑ์ค€ 2156๋ฒˆ ํฌ๋„์ฃผ ์‹œ์‹ - ํŒŒ์ด์ฌ(Python)  (0) 2021.09.15
[BOJ] ๋ฐฑ์ค€ 1932๋ฒˆ ์ •์ˆ˜ ์‚ผ๊ฐํ˜• - ํŒŒ์ด์ฌ(Python)  (0) 2021.09.14
    'Algorithm/๐Ÿ“˜ Baekjoon Judge' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€์ด๋‹ค
    • [BOJ] ๋ฐฑ์ค€ 1012๋ฒˆ ์œ ๊ธฐ๋† ๋ฐฐ์ถ” - ํŒŒ์ด์ฌ(Python)
    • [BOJ] ๋ฐฑ์ค€ 14501๋ฒˆ ํ‡ด์‚ฌ - ํŒŒ์ด์ฌ(Python)
    • [BOJ] ๋ฐฑ์ค€ 10844๋ฒˆ ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜ - ํŒŒ์ด์ฌ(Python)
    • [BOJ] ๋ฐฑ์ค€ 2156๋ฒˆ ํฌ๋„์ฃผ ์‹œ์‹ - ํŒŒ์ด์ฌ(Python)
    J1Yun
    J1Yun
    ๊ฐœ๋ฐœ ๊ด€๋ จ ๊ธฐ์ˆ  ๋ฐ ๊ณต๋ถ€ ๋‚ด์šฉ ๊ธฐ๋ก์žฅ

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