백준 14720 우유 축제

백준 14720 우유 축제

14720번: 우유 축제

dp문제이다. 저번에 이 문제 심화버전 우유 도시 풀다가 도저히 못풀겠어서 놔뒀는데

이 문제 풀고나니까 어떻게 풀어야 되는지 감이 잡힌다.

이 문제의 포인트는 

1.무조건 딸기 우유 부터 시작해야한다.

만약에 2 2 2 2 2 이런식으로 갔다면 영학이는 우유를 하나도 먹을 수 없음

그래서 0으로 시작하는 것부터 찾아야 한다.

저번에 우유 도시 풀다가 깨달음...

​

그리고 우유의 상태를 표시하기 위해서 우유는 귀찮지만 2차원 배열로 만들었음 

dp는 1차원으로 만들었음

 

 

#include <iostream>
​
using namespace std;
​
int main(void)
{
    int n;
    cin >> n;
    int m[1001][3];
    int dp[1001];
​
    for (int i = 1; i <= n; ++i) {
        int milk;
        cin >> milk;
        if (milk == 0) {
            m[i][0] = 1;
            m[i][1] = 0;
            m[i][2] = 0;
        }
        else if (milk == 1) {
            m[i][0] = 0;
            m[i][1] = 1;
            m[i][2] = 0;
        }
        else {
            m[i][0] = 0;
            m[i][1] = 0;
            m[i][2] = 1;
        }
    }
​
    int s;
    
    for (s = 1; s <= n; ++s) {
        if (m[s][0] > 0) {
            break;
        }
    }
    if (s <= n)
        dp[s] = 1;
    else
        dp[n] = 0;
    if (m[s][0] == 0 && n == 0)
        dp[s] = 0;
    
    int k = 1;
    for (int i = s+1; i <= n; ++i) {
        if (m[i][(k % 3)] > 0) {
            dp[i] = dp[i - 1] + m[i][(k % 3)];
            k++;
        }
        else
            dp[i] = dp[i - 1];
    }
​
    cout << dp[n] << endl;
​
    return 0;
}​