백준] 2156 : 포도주 시식

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

2156번: 포도주 시식

 

문제  : 

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

 

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

 

 

입력  : 

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

 

출력  : 

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

 

 

 

 

접근 방법

1. 초기화

- 배열인 dp와 arr는 10001로 만들고, 전역변수로 선언해서 0으로 초기화해준다.
- arr에 주어진 포도주의 양을 입력 받고, (i는 1부터 시작해서 <=n까지)
  dp[1] = arr[1], dp[2] = arr[1] + arr[2]... 로 초기화 해준다.

2. dp

- 연속으로 세 번은 마실 수 없다는 부분을 잘 생각해야 한다.

- 따라서

위의 1, 2, 3 중 최대값을 찾아주면 된다.

 

// 틀림

#include <iostream>
using namespace std;

int Max(int a, int b, int c){
	if( a > b ){
		if(c > a){
			return c;
		}else{
			return a;
		}
	}else if( b > c){
		return b;
	}
}

int dp[10001], arr[10001];

int main() {
	
	int n = 0;
	
	cin >> n;
	
	for(int i = 0; i < n; i++){ // i = 1부터
		cin >> arr[i];
	}
	
	dp[0] = 0;
	dp[1] = arr[1];
	dp[2] = dp[1] + arr[2];
	
	for(int i = 3; i <= n; i++){
		dp[i] = Max( dp[i - 3] + arr[i - 1] + arr[i], dp[i - 1], dp[i - 2] + arr[i]);
	}
	
	cout << dp[n];
	
	return 0;
}

 

// 맞음

#include <iostream>
using namespace std;

int arr[10001], dp[10001];

int Max(int a, int b){
	return a > b ? a : b;
}

int main()
{

	int n;

	cin >> n;
	
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
	
	for (int i = 3; i <= n; i++) {
		dp[i]= Max(dp[i - 3] + arr[i] + arr[i - 1], dp[i - 2] + arr[i]);
		dp[i]= Max(dp[i - 1], dp[i]);
		
	}

	cout << dp[n];
}

 

 

정답 코드

#include <iostream>
using namespace std;

int arr[10001], dp[10001];

int Max(int a, int b){
	return a > b ? a : b;
}

int main()
{

	int n;

	cin >> n;
	
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
	
	for (int i = 3; i <= n; i++) {
		dp[i]= Max(dp[i - 3] + arr[i] + arr[i - 1], dp[i - 2] + arr[i]);
		dp[i]= Max(dp[i - 1], dp[i]);
		
	}

	cout << dp[n];
}

 

 

 

 

참고한 블로그

[백준] 2156 - 포도주 시식

백준 2156번 포도주 시식 [DP] :: 마이구미

[BOJ] 백준 2156 포도주시식-java