백준 14720 - 우유 축제

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

14720번: 우유 축제

 

영학이가 우유를 마시는 규칙에 따라 각 상태를 기억하는 방식으로 우유 가게를 순회하면 쉽게 풀 수 있다.

 

다음과 같은 배열을 구성해보자.

int milk[3] {1, 2, 0};

이는 영학이가 0, 1, 2 중 한가지의 우유를 마셨을 때 다음 우유는 어떤 것을 먹어야 하는지 나타내는 배열이다.

 

이 배열을 이용해 입력을 순회하는 함수를 구성하면 쉽게 해결할 수 있다.

int travel(int idx, int next, vector<int> &shop, int ret)
{
    int range(shop.size());
    
    // 상점을 모두 지나친 경우 return
    if (idx == range)
        return ret;
    
    // 규칙에 따라 우유를 먹었는지에 따라 재귀함수 호출
    if (shop[idx] == next)
        return travel(idx + 1, milk[next], shop, ret + 1);
    else
        return travel(idx + 1, next, shop, ret);
}

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int milk[3] {1, 2, 0};

int travel(int idx, int next, vector<int> &shop, int ret);

int main()
{
    int n; cin >> n;
    vector<int> store(n);
    
    for (int i = 0; i < n; ++i)
        cin >> store[i];
    
    cout << travel(0, 0, store, 0);
}

int travel(int idx, int next, vector<int> &shop, int ret)
{
    int range(shop.size());
    
    if (idx == range)
        return ret;
        
    if (shop[idx] == next)
        return travel(idx + 1, milk[next], shop, ret + 1);
    else
        return travel(idx + 1, next, shop, ret);
}