[Baekjoon] 2156 - 포도주 시식 / C++
> 문제
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
> 풀이
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
글 읽기 - 와인을 마시지 않는 경우가 왜 필요한가요?
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
비슷했다고 생각했던 문제
https://www.acmicpc.net/problem/2579
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
> 코드
// 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;
}