16968 / 차량 번호판 1

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

16968번: 차량 번호판 1

 

 

 

 

 

Solution 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

string s;

int main()
{
    FASTio;
    cin >> s;
    int a = 10;
    int b = 26;
    int sum = 1;

    for(int i=0;i<s.length();)
    {   
        if(s[i]=='d')
        {   
            int index = i+1;
            int ori = a-1;
            sum *= a;
            while(1)
            {
                if(s[index]!='d')
                {
                    i = index;
                    break;
                }
                else
                {   
                    sum *= ori;
                    index++;
                } 
            }

        }
        else if(s[i]=='c')
        {
            int index = i+1;
            int ori = b-1;
            sum *= b;
            while(1)
            {
                if(s[index]!='c')
                {
                    i = index;
                    break;
                }
                else
                {   
                    sum *= ori;
                    index++;
                } 
            }
        }
    }

    cout << sum;

    return 0;
}

 

숫자 0~9 총 10가지 경우이고,

문자 a~z  총 26가지 경우이다.

 

하지만, 같은 형식이 연속해서 나오는 경우 이 전에 나온 문자는 또 나올 수 없다는 조건이 있다.

 

예를들어 dddc의 경우에는 

 

첫번째 문자에 나올 수 있는 경우는 10가지, 두번째 문자에 나올 수 있는 경우는 앞에 나온 문자를 제외한 9가지, 세번째 문제에 나올 수 있는 경우는 두번째 문자에 나온 문자를 제외한 9가지,  네번째 문자에 나올 수 있는 경우는 26가지 

 

총 10 * 9 * 9 * 26 가지이다.

 

따라서 문자가 연속해서 나오는 경우에는 숫자인 경우 연속해서 나오지 않을때까지 9를 곱해주었고, 문자의 경우 25를 곱해 주었다.

  

 

 

Solution 2 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 
using namespace std;

string s;

int ans(int index, char before)
{   
    int sum = 0;

    if(s.length()==index)
    {
        return 1;
    }

    char start,end;

    if(s[index]=='c')
    {
        start = 'a';
        end = 'z';
    }
    else if (s[index]=='d')
    {
        start = '0';
        end = '9';
    }

    for(char c = start; c <= end ; c++)
    {
        if(c != before)
        {   
            sum += ans(index+1,c);
        }

    }

    return sum;
    

}
int main()
{
    FASTio;
    cin >> s;
    cout << ans(0,' ');
    return 0;
}

입력받은 이전 문자와 같은 경우를 제외한 모든 경우를 재귀적으로 구해주었다.