[Baekjoon] 2156 - 포도주 시식 / C++

> 문제

< 썸네일 >

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

2156번: 포도주 시식

 

 

2156번: 포도주 시식

 

 

2156번: 포도주 시식

---

> 풀이

1. 첫 번째 풀이 : 처음에는 이전의 계단 오르기 문제랑 동일하다고 생각해서 그때의 문제풀이를 바탕으로 arr[i]에 wines[i-1] + arr[i-3] 이랑arr[i-2]랑 더 큰 수를 더하는 방법을 사용했다.
그런데 이렇게 문제를 풀면 반례가 존재하여 문제풀이에 성공할 수 없었다.

 

 

2. 두 번째 풀이 : 질문에 있던 반례를 참고하여 1.에서 사용했던 방법은 2개의 포도주를 건너뛸때 반례에 걸린다는 것을 이해했다. 그래서 arr[i] 에 wines[i] + wines[i-1] + arr[i-3] 이랑 wines[i] + arr[i-2], wines[i] + wines[i-1] + arr[i-4]중 제일 큰 수를 더해주는 걸로 고쳤다.

 

* 그리고 arr[n-1] 이랑 arr[n-2]랑 마지막에 비교해서 출력해줘야 하는데, 그건 arr[n-2]가 최고인 경우도 존재하기 때문이다.(arr[n-1]에 1을 마지막에 붙인 경우)

---

> 느낀 점

같은 유형에 비슷한 조건이라고 해서 문제풀이까지 완전히 똑같지는 않다는 것을 깨닫게 되었다. 앞으로는 비슷한 유형의 문제를 보면 그 풀이를 그대로 따라하지 맣고 참고만 하여 새로운 문제풀이 방법을 만들어낸다는 생각으로 PS를 진행해야겠다.

도움을 얻었던 글

https://www.acmicpc.net/board/view/64747

글 읽기 - 와인을 마시지 않는 경우가 왜 필요한가요?

비슷했다고 생각했던 문제

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

2579번: 계단 오르기

---

> 코드

// Baekjoon No. 2156 포도주 시식 220801~ 220807
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, i;
    scanf("%d", &n);
    vector<int>wines(n, 0);
    vector<int>arr(n, 0);
    for(i = 0; i < n; i++)
        scanf(" %d", &wines[i]);
    
    // 초깃값만 각각 설정
    arr[0] = wines[0];
    if(n > 1)
        arr[1] = wines[0] + wines[1];
    if(n > 2)
        arr[2] = max(wines[0], wines[1]) + wines[2];
    if(n > 3)
        arr[3] = max(wines[3] + wines[2] + wines[0], wines[3] + arr[1]);
    // wines[i] + wines[i-1] + arr[i-3], wines[i] + wines[i-1] + arr[i-4], wines[i] + arr[i-2] 이렇게 3개 확인해야함.
    // 5 5 1 1 5 5 같은 반례 존재.
    for(i = 4; i < n; i++){
        arr[i] = max(max(wines[i] + wines[i-1] + arr[i-3], wines[i] + arr[i-2]), wines[i] + wines[i-1] + arr[i-4]);
    }

    if(n > 1)
        printf("%d", max(arr[n-2], arr[n-1]));
    else
        printf("%d", arr[0]);
    return 0;
}