이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

백준 21758 - 꿀 따기 (파이썬)

  • 2025.03.14 02:08
  • Programming/백준
글 작성자: pental

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

풀이

누적합 배열을 사용하며, 벌과 꿀통의 배치를 최적화하여 최대 꿀 수확량을 계산하는 문제이다.

먼저 누적합 계산을 위해서 초기화를 진행한다.

psum = [0] * N
for i in range(N):
    if i == 0:
        psum[i] = A[i]
    else:
        psum[i] = psum[i - 1] + A[i]
  1. 첫번째 경우 (벌이 양 끝, 꿀통이 중간한 가정)
    • 첫번째 벌은 0번 위치 (A[0])
    • 두번째 벌은 N - 1번 위치 (A[N - 1])
    • 꿀통은 중간에 있는 최대 꿀량의 벌통
      1. max(A[1:-1]) → (첫 번째와 마지막을 제외한 부분에서 최댓값)
  2. answer = psum[N - 2] - psum[0] + max(A[1:-1])
  3. 두번째 경우 (벌 - 벌 - 꿀통 가정)
    • 첫 번째 벌: A[0] (맨 왼쪽)
    • 두 번째 벌: A[i] (중간)
    • 꿀통: A[N-1] (맨 오른쪽)
    a = psum[N - 1] - psum[0] - A[i]
    • 첫 번째 벌이 벌통 A[0]에서 출발하여 끝까지 가면서 얻는 꿀.
    • 단, A[i]에 도착하면 그 벌이 꿀을 가져가지 않음.
    b = psum[N - 1] - psum[i]
    • 두 번째 벌이 A[i]에서 시작하여 끝까지 가면서 얻는 꿀.
  4. for i in range(1, N - 1): a = psum[N - 1] - psum[0] - A[i] b = psum[N - 1] - psum[i] answer = max(answer, a + b)
  5. 세번째 경우 (꿀통 - 벌 - 벌 가정)
    • 꿀통: A[0] (맨 왼쪽)
    • 첫 번째 벌: A[i] (중간)
    • 두 번째 벌: A[N-1] (맨 오른쪽)
    꿀 수확량
    • 두 번째 벌이 A[N-1]에서 출발하여 A[i]까지 가면서 얻는 꿀.
    • A[i]는 벌이 꿀을 먹지 못함.
    b = psum[i - 1]
    • 첫 번째 벌이 A[0]에서 A[i]까지 가면서 얻는 꿀.
  6. a = psum[N - 2] - A[i]
  7. for i in range(1, N - 1): a = psum[N - 2] - A[i] b = psum[i - 1] answer = max(answer, a + b)

시간 복잡도 분석

  1. 누적합 계산 : O(N)
  2. 각 경우 반복문 : O(N)
  3. 총 시간 복잡도 : O(N)

코드

# 백준 21758 - 꿀 따기
# 분류 : 그리디, 누적합

N = int(input())
A = list(map(int, input().split()))

psum = [0] * N
for i in range(N) :
    if i == 0 :
        psum[i] = A[i]
    else :
        psum[i] = psum[i - 1] + A[i]

answer = psum[N - 2] - psum[0] + max(A[1:-1])

for i in range(1, N - 1) :
    a = psum[N - 1] - psum[0] - A[i]
    b = psum[N - 1] - psum[i]
    answer = max(answer, a + b)

for i in range(1, N - 1) :
    a = psum[N - 2] - A[i]
    b = psum[i - 1]
    answer = max(answer, a + b)

print(answer)
저작자표시 비영리 (새창열림)

'Programming > 백준' 카테고리의 다른 글

백준 17219 - 비밀번호 찾기  (1) 2025.03.15
백준 9375 - 패션왕 신해빈 (파이썬)  (0) 2025.03.15
백준 1302 - 베스트셀러 (파이썬)  (0) 2025.03.13
백준 1092 - 배 (파이썬)  (0) 2025.03.12
백준 2075 - N번째 큰 수 (파이썬)  (0) 2025.03.11

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 백준 17219 - 비밀번호 찾기

    백준 17219 - 비밀번호 찾기

    2025.03.15
  • 백준 9375 - 패션왕 신해빈 (파이썬)

    백준 9375 - 패션왕 신해빈 (파이썬)

    2025.03.15
  • 백준 1302 - 베스트셀러 (파이썬)

    백준 1302 - 베스트셀러 (파이썬)

    2025.03.13
  • 백준 1092 - 배 (파이썬)

    백준 1092 - 배 (파이썬)

    2025.03.12
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (444) N
    • Forensics (104)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (23)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (253) N
      • C (10)
      • Python (11)
      • 백준 (199) N
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • 백준
  • 포렌식
  • 파이썬
  • axiom
  • 디지털포렌식
  • pental
  • 프로그래머스
  • Forensics
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바