boj_2579 / 2156 포도주 시식하며 계단 오르기

먼저 계단오르기부터

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

2579번: 계단 오르기

dp 개념을 이해하는게 중요했다.

*dp : 한번 계산해둔거는 다시 계산하지 않는 것이 핵심.

//boj 2579번 계단 오르기...
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 301

void counting_stairs();

int n;//number of stairs
int arr[MAX];
int dp[MAX];

int main(){
    //cout<<"enter how many stairs";
    cin>>n;
    for(int i = 1; i <= n; i++){
        //cout<<"\nenter " << i <<"stair point\n";
        cin >> arr[i];
    }
    //for(int i = 1; i <= n; i++){
        //cout<<" | "<<arr[i]<<" | ";
    //}
    counting_stairs();
    return 0;
}
void counting_stairs(){
    /*
    *계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
    *연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
    *마지막 도착 계단은 반드시 밟아야 한다.
    */
   dp[1] = arr[1];
   dp[2] = arr[1]+arr[2];
   dp[3] = max(arr[1]+arr[3], arr[2]+arr[3]);

   for(int i=4; i<=n; i++){
       dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
   }
   cout <<dp[n];
}

//boj 2579번 계단 오르기...
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 301 //최대가 300이고, 1부터 시작함.

void counting_stairs();

int n;//number of stairs
int arr[MAX];
int dp[MAX]; //dp 배열엔 그 값에서 가질 수 있는 최댓값이 들어감.

int main(){
    //cout<<"enter how many stairs";
    cin>>n;
    for(int i = 1; i <= n; i++){
        //cout<<"\nenter " << i <<"stair point\n";
        cin >> arr[i];
    }
    //for(int i = 1; i <= n; i++){
        //cout<<" | "<<arr[i]<<" | ";
    //}
    counting_stairs();
    return 0;
}
void counting_stairs(){
   dp[1] = arr[1]; --> 하나는 무조건 arr[1]이 최댓값이다.
   dp[2] = arr[1]+arr[2]; --> 2에서도 최댓값이 arr[1]+arr[2]가 최댓값이다.
   dp[3] = max(arr[1]+arr[3], arr[2]+arr[3]); --> 3번째까지의 최댓값인데 여기선 규칙중에서 3개 연속불가니까 둘중 더 큰거 선택해서 가게 함.
   for(int i=4; i<=n; i++){
       dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
   }
   cout <<dp[n];
}

어디에서 막혔나?
:이걸 n개로 생각하니까 막혔음

왜 이생각을 못했나? :
n개로 생각을 했기에 너무 막연했음.

다음엔 어떻게 접근해야하는가? :
그냥 써가면서 쭉 늘여가다가. 어느정도 와서 반복된다 싶으면 거기서부터 n으로 바꿔서 풀어야 한다.

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

2156번: 포도주 시식

//약중에 제일 맛있고 밥중에 제일 몸에 좋은 것
#include <iostream>
using namespace std;
#define MAX 10001

int n;
int arr[MAX];
int dp[MAX];
int maxnum;

void counting_drinks();

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    counting_drinks();
    return 0;
}

void counting_drinks(){
    dp[1] = arr[1];
    dp[2] = arr[1]+arr[2];
    dp[3] = max(max(arr[1]+arr[2] , arr[1]+arr[3]) , arr[2]+arr[3]);
    for(int i = 4; i <= n; i++){
        dp[i] = max(dp[i-2]+arr[i],dp[i-3]+arr[i-1]+arr[i]);
        dp[i] = max(dp[i], dp[i-1]);
    }

    //output
    for(int j = 0; j < n; j++){
        if(dp[j]<=dp[j+1]){
            maxnum = dp[j+1];
        }
    }
    cout<<maxnum;
}

//약중에 제일 맛있고 밥중에 제일 몸에 좋은 것
#include <iostream>
using namespace std;
#define MAX 10001 //1부터 시작함.

int n; //편리를 위해 전역으로
int arr[MAX];
int dp[MAX];
int maxnum;

void counting_drinks();

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    counting_drinks();
    return 0;
}

void counting_drinks(){
    dp[1] = arr[1];
    dp[2] = arr[1]+arr[2];
    dp[3] = max(max(arr[1]+arr[2] , arr[1]+arr[3]) , arr[2]+arr[3]); //여기도 중요함,
    for(int i = 4; i <= n; i++){
        dp[i] = max(dp[i-2]+arr[i],dp[i-3]+arr[i-1]+arr[i]);
        dp[i] = max(dp[i], dp[i-1]); //이 부분이 중요하다. 이걸 생각을 못했음. 아니 근데 이걸 안보고 생각하는건 쉽지 않잖아요
    }

    //output
    for(int j = 0; j < n; j++){
        if(dp[j]<=dp[j+1]){
            maxnum = dp[j+1];
        }
    }
    cout<<maxnum;
}

 

틀렸던 EU
1. 일반화를 하지 않았고
2. 알고리즘 적으면서 정리도 안해봤으며
3. 왜 앞앞까지 보았는가...
이거 닫는거 왜 없어

-실패한 예시

 

조금만 생각해서 이런걸 만들었고...

이렇게 일단 써보고. 쓰다가 알았다.

dp3의 경우 굳이 자기 자신을 포함할 필요가 없으니까

102 402가 최댓값이 아니고 dp2값과 같은 500이 최댓값이다.

이걸 코드에 적용하기 위해서는 그냥 간단하게

한칸 앞 dp값이랑 지금 dp값이랑 어느게 젤 큰지만 알 수 있게 해주는 코드만 추가하면 끝이다.

 

보면 알겠는데 만들자니 어렵다.