[백준] 2228번 구간 나누기 _ Python

2023. 11. 24. 14:51·Algorithms/DP

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

 

[초기 접근 방법]

- 문제 이해 잘못

(2번 조건을 무시하고 '배열 구간 나누기'로 풀었다.)

 

그래도 이 때 문제 풀이를 적자면,

골드3 문제인데, dp[]가 1차원 배열이라니 뭔가 이상했어...

 

 

 

[생각]

틀리고 '반례가 있을까?' 질문 게시판을 찾아보다가 접근이 아예 잘못된 것 같아서 구글링을 했다.

 

1. dp[i][j] : i개의 배열로, j개의 구간을 선택했을 때 구간합 최댓값

     - 이 때 주의할 점은 배열을 이루는 수에는 음수도 있기에, -float('inf')로 초기화한다.

 

2. 점화식

1) 현재 구간을 유지하면서, i번째 값을 포함시키지 않았을 경우

dp[i][j] = max(dp[i][j], dp[i-1][j])

 

2) 새로운 구간으로 i번째 값을 포함시켰을 경우,

     최소 간격이 있어야 하므로 k-2로 설정,

     간격을 i에서부터 i-2, 즉 최소간격 2까지 반복하며

     현재 i번째까지의 dp[i][j] 값을 최댓값으로 설정한다.

dp[i][j] = max(dp[i][j], dp[k-2][j-1] + sum[i] - sum[k-1])

 

 

"dp + 구간합" 문제로,

2번째 점화식에서 간격을 i에서부터 2까지 설정하며 최댓값을 구하는 접근이 이해하는데 시간이 걸렸다.

 

 

 

[코드]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
lst = [0] + [int(input()) for _ in range(N)]

# dp[i][j] = i개의 배열로, j개의 구간을 선택했을 때 구간합 최댓값
    # 배열을 이루는 수에는 음수도 있음
dp = [[0] + [-float('inf')] * M for _ in range(N+1)]

# 점화식
# 1. 구간을 유지하면서 i번째 값을 포함시키지 않았을 경우
# dp[i][j] = max(dp[i][j], dp[i-1][j])
# 2. 새로운 구간으로 i번째 값을 포함시켰을 경우, 하지만 간격이 있어야 하므로
# dp[i][j] = max(dp[i][j], dp[k-2][j-1] + sum[i] - sum[k-1])

# 구간합 구하기
rangeSum = []
sumI = 0
for i in range(N+1):
    sumI += lst[i]
    rangeSum.append(sumI)

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = dp[i - 1][j]
        for k in range(1, i+1):
            # k>=2일 때, 구간 간격을 띄울 수 있음
            if k >= 2:
                dp[i][j] = max(dp[i][j], dp[k-2][j-1] + rangeSum[i] - rangeSum[k-1])

            # 1개의 구간일 때는 총합 값이다.
            elif j == 1:
                dp[i][j] = max(dp[i][j], rangeSum[i])

print(dp[N][M])
저작자표시 (새창열림)

'Algorithm > DP' 카테고리의 다른 글

[백준] 7579번 앱 _ Python  (0) 2024.02.23
[백준] 14925번 목장 건설하기 _ Python  (1) 2024.01.30
[백준] 17626번 Four Squares _ Python  (0) 2023.11.23
[백준] 5557번 1학년 _ Python  (1) 2023.11.21
[백준] 17626번 Four Squares _ Python  (0) 2023.11.17
'Algorithms/DP' 카테고리의 다른 글
  • [백준] 7579번 앱 _ Python
  • [백준] 14925번 목장 건설하기 _ Python
  • [백준] 17626번 Four Squares _ Python
  • [백준] 5557번 1학년 _ Python
wch_t
wch_t
  • wch_t
    끄적끄적(TIL)
    wch_t
  • 글쓰기 관리
  • 전체
    오늘
    어제
    • 분류 전체보기 (171)
      • Architecture (0)
      • Algorithm (67)
        • Math (5)
        • Simulation (1)
        • Data Structure (4)
        • DP (7)
        • Brute Fource (10)
        • Binary Search (6)
        • Greedy (2)
        • Graph (11)
        • Mst (1)
        • Shortest path (10)
        • Two Pointer (1)
        • Tsp (3)
        • Union Find (2)
        • Mitm (1)
      • CS (2)
        • 데이터베이스 (5)
        • 네트워크 (5)
      • DB (6)
      • DevOps (17)
        • AWS (9)
        • Docker (1)
        • CI-CD (5)
      • Error (1)
      • Project (0)
        • kotrip (0)
      • Spring (59)
        • 끄적끄적 (5)
        • 기본 (9)
        • MVC 1 (7)
        • MVC 2 (11)
        • ORM (8)
        • JPA 1 (7)
        • JPA 2 (5)
        • Spring Data Jpa (7)
      • Test (2)
      • TIL (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    form_post
    apache poi
    docker: not found
    docker
    spring-cloud-starter-aws-secrets-manager-config
    view algorithm
    백준 17289 파이썬
    애플
    백준 3015 파이썬
    Merge
    response_mode
    spring-cloud-starter-bootstrap
    Sxssf
    aws secrets manager
    TempTable
    백준 17299 파이썬
    scope
    Jenkins
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
wch_t
[백준] 2228번 구간 나누기 _ Python
상단으로

티스토리툴바