[BOJ] 꿀 따기 21758번 C++

2024. 5. 1. 15:30· Algorithm
목차
  1. 접근 방식
  2. 코드

 

문제

아래와 같이 좌우로 𝑁개의 장소가 있다.

 

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

  1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
  2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 4+1+4+9+9=27의 꿀을 따서, 전체 꿀의 양은 54가 된다.

 

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 9+4+4+9+9=35의 꿀을 따고 오른쪽 장소에서 출발한 벌은 4+9+9=22의 꿀을 따므로, 전체 꿀의 양은 57이 된다.

 

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 장소의 수 𝑁이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

출력

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

 

 

접근 방식

 

처음에  벌들과 벌통이 놓일 수 있는 모든 경우의 수를 구해 최대 꿀의 양을 구했더니 시간 초과가 발생했다

 

그래서 다른 분들 풀이를 살펴보니

이 문제는 해답을 3가지 경우로 간추려 풀 수 있는 문제임을 깨달았다

 

벌과 벌통의 위치의 가짓수는 세가지다

1. 벌 벌 벌통

2. 벌 벌통 벌

3. 벌통 벌 벌

 

이때 세가지 모두 가장 왼쪽, 오른쪽에 있는 것들은 1, N에 있어야지 최대의 꿀의 양을 가질 수 있다

그리고 구현시 주의할 점은 1,3번의 경우 각각 제일 왼쪽에 있는 벌과 제일 오른쪽에 있는 벌의 꿀의 양을 구할 때

다른 벌의 위치에 있는 꿀을 빼주어야 한다!

 

이를 코드로 구현하면 다음과 같다

 

코드

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int N;
ll ans = 0;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N;
    vector<ll> pSum(N+1), honeys(N+1);
    pSum[0] = 0;
    for(int i=1; i<=N; i++) {
        cin>>honeys[i];
        pSum[i] = honeys[i] + pSum[i-1];
    }

    for(int i=2; i<N; i++) {
        // 1. 벌(1) 꿀통(i) 벌(N)
        ans = max(ans, pSum[i] - pSum[1] + pSum[N-1] - pSum[i-1]);
        // 2. 벌(1) 벌(i) 꿀통(N)
        ans = max(ans, pSum[N] - pSum[1] + pSum[N] - pSum[i] - honeys[i]);
        // 3. 꿀통(1) 벌(i) 벌(N)
        ans = max(ans, pSum[N-1] - pSum[0] + pSum[i-1] - pSum[0] - honeys[i]);
    }

    cout<<ans;
}

 

 

생각보다 이해가 잘 안되서 시간이 매우 오래걸린 문제였다...

'Algorithm' 카테고리의 다른 글

[BOJ] 파일 합치기 3 13975번 C++  (0) 2024.05.06
[BOJ] 우체국 2141번 C++  (0) 2024.05.05
[BOJ] 배 1092번 C++  (0) 2024.04.29
[BOJ] 최소 회의실 개수 19598번 C++  (1) 2024.04.29
[BOJ] A → B 16953번 C++  (1) 2024.04.27
  1. 접근 방식
  2. 코드
'Algorithm' 카테고리의 다른 글
  • [BOJ] 파일 합치기 3 13975번 C++
  • [BOJ] 우체국 2141번 C++
  • [BOJ] 배 1092번 C++
  • [BOJ] 최소 회의실 개수 19598번 C++
따봉치치
따봉치치
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 탐욕 알고리즘
  • BFS
  • 그리디
  • 우선순위 큐
  • javascript
  • 데이터베이스
  • BOJ
  • Greedy
  • 누적합
  • CS
  • Stack
  • 모던 리액트 딥다이브
  • 백트래킹
  • Fe
  • 리액트
  • dp
  • 알고리즘
  • 그래프 탐색
  • react
  • 투 포인터
  • typescript
  • 백준
  • TOPCIT
  • 자바스크립트
  • C++
  • 완전탐색
  • 자료구조
  • 문자열
  • 모던 자바스크립트 딥다이브
  • 스택

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 꿀 따기 21758번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.