고도고도
🍎🍏
고도고도
전체 방문자
7,922
오늘
2
어제
26
  • 분류 전체보기 (149) N
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (43) N
      • TIL (16)
      • Android (6)
      • Kotlin (4)
      • Flutter (9) N
      • Node.js (5)
      • Error (3) N
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (50)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (7)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

인기 글

  • [TIL] 22.03.13
    2022.03.13
    [TIL] 22.03.13
  • [문자열 / Kotlin] 2020 KAKAO⋯
    2022.03.11
    [문자열 / Kotlin] 2020 KAKAO⋯
  • [TIL] 22.03.20
    2022.03.20
    [TIL] 22.03.20
  • [퍼듀 일기] 어느덧 한 달째
    2022.03.01
    [퍼듀 일기] 어느덧 한 달째
  • [퍼듀 일기] 적응 완료
    2022.03.05
    [퍼듀 일기] 적응 완료

최근 글

  • [Flutter] ModalBottomSheet가⋯
    2022.08.09
    [Flutter] ModalBottomSheet가⋯
  • [Error / Gradle] The current⋯
    2022.08.09
    [Error / Gradle] The current⋯
  • [Flutter / Dart] What is Equa⋯
    2022.08.06
    [Flutter / Dart] What is Equa⋯
  • [Flutter] BLoC 패턴으로 자동⋯
    2022.07.26
    [Flutter] BLoC 패턴으로 자동⋯
  • [Flutter / Dart] What is Sing⋯
    2022.07.21
    [Flutter / Dart] What is Sing⋯

최근 댓글

  • 잘보고 갑니다~
    개갓세
  • 좋은 글이네요
    날인로세
  • 잘 보고 갑니다^^
    프로퍼티
hELLO · Designed By 정상우.
고도고도

🍎🍏

[동적 계획법 1] [C++] 2156번. 포도주 시식
✍️ 코테 준비/Dynamic Programming

[동적 계획법 1] [C++] 2156번. 포도주 시식

2021. 1. 25. 11:10

www.acmicpc.net/problem/2156

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

 

 

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.


해결 방법

포도주를 마실 수 있는 방법은 어떻게 될까?

 

dp를 n번째 잔까지 마실 때 가장 많은 양의 포도주, grape를 n번째 잔의 포도주라고 가정하자.

 

dp[0] = 0

dp[1] = 첫번째 잔만 있을 때 = grape[1]

dp[2] = 첫번째 잔과 두번째 잔이 있을 때 = grape[1] + grape[2]

 

dp[3] = 첫번째 잔과 두번째 잔, 세번째 잔이 있을 때

(dp[3]부터는 3개의 연속된 잔을 선택할 수 없으므로 다른 규칙을 적용해야 한다.)

 

dp[1] + grape[3] (dp[2]는 grape[1] + grape[2] 이므로 dp[2] + grape[3]을 하게 되면 연속된 세 잔이다.)

dp[0] + grape[2] + grape[3]

 

두 가지의 방법이 나올 수 있다. 따라서 둘 중 더 큰 값을 dp에 저장하면 된다.

 

이를 점화식으로 나타내면 다음과 같다.

dp[i] = max(dp[i-2] + grape[i], dp[i-3] + grape[i-1] + grape[i]) (i ≥ 3)

 

하지만...

 

 

계속 "틀렸습니다"가 나오는 것이었다... 점화식은 문제가 없어보이는데... 결국 구글링을 통해서 다른 블로그를 참고했다.

 

마시지 않는 경우도 생각했어야했는데... 이를 생각을 못했다.

 

따라서 최종적인 점화식은

dp[i] = max(max(dp[i-1], dp[i-2] + grape[i]), dp[i-3] + grape[i-1] + grape[i]) (i ≥ 3) 가 된다.

 

최종 코드는

 


아래 문제는 이번 문제보다 상당히 유사한 문제이다.

'동적 계획법 1'을 처음부터 풀었다면 먼저 풀어봤을 문제이지만 참고하면 좋을 것 같다.

 

codekodo.tistory.com/30

 

[동적 계획법 1] [C++] 2579번. 계단 오르기

www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/proble..

codekodo.tistory.com

 

저작자표시

'✍️ 코테 준비 > Dynamic Programming' 카테고리의 다른 글

[동적 계획법 1] [C++] 11054번. 가장 긴 바이토닉 부분 수열  (0) 2021.02.01
[동적 계획법 1] [C++] 11053번. 가장 긴 증가하는 부분 수열  (0) 2021.01.25
[동적 계획법 1] [C++] 2156번. 포도주 시식  (0) 2021.01.25
[동적 계획법 1] [C++] 10844번. 쉬운 계단 수  (0) 2021.01.24
[동적 계획법 1] [C++] 1463번. 1로 만들기  (0) 2021.01.19
[동적 계획법 1] [C++] 2579번. 계단 오르기  (0) 2021.01.14
    '✍️ 코테 준비/Dynamic Programming' 카테고리의 다른 글
    • [동적 계획법 1] [C++] 11054번. 가장 긴 바이토닉 부분 수열
    • [동적 계획법 1] [C++] 11053번. 가장 긴 증가하는 부분 수열
    • [동적 계획법 1] [C++] 10844번. 쉬운 계단 수
    • [동적 계획법 1] [C++] 1463번. 1로 만들기
    C++, 동적 계획법 1, 백준
    고도고도
    고도고도
    좋아하는 것을 하자\n 스위프트 찍먹중\n 광고 없는 블로그
    댓글쓰기
    다음 글
    [동적 계획법 1] [C++] 11053번. 가장 긴 증가하는 부분 수열
    이전 글
    [동적 계획법 1] [C++] 10844번. 쉬운 계단 수
    • 이전
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • ···
    • 13
    • 다음