sicily 1001. Alphacode dp

1260 단어 Alpha
동적 기획을 보고 dp에 대한 대략적인 이해를 했습니다. 이 문제는 그동안 끊겼고 처음에는 검색으로도 했습니다.
0에 대한 처리에 주의해야 한다. 방정식을 잘못 열거하기 시작한다. WA는 여러 번
dp 방정식은 a[n] = a[n-1] + a[n-2]이고 입력한 문자열은 한 번에 X1X2X3... Xn...
Xn = 0 시, a[n] = a[n-2]
땡땡!0시,
만약에 X(n-1)와 X(n)로 구성된 수가 26보다 크면 a[n]=a[n-1].
만약 X(n-1)와 X(n)로 구성된 수<=26,
x(n-1)가 0이 아니면 a[n]=a[n-1]+a[n-2]
x(n-1)=0시, a[n]=a[n-1]
 
#include <iostream>

#include <string>

#define MAX 100000

using namespace std;



int main()

{

	string num;

	long long a[MAX];

	int size;

	int n;

	while (cin >> num && num != "0")

	{

		size = num.length();

		a[0] = 1;

		a[1] = 1;



		if (size == 1)

		{

			cout << "1" << endl;

			continue;

		}

		

		//      	

		n = (num[0]-'0')*10 + num[1]- '0';

		if (n <= 26 && num[1] != '0')

			a[1] = 2;

			

		for (int i = 2; i < size; i++)

		{

			if (num[i] == '0')

				a[i] = a[i-2];

			else

			{

				a[i] = a[i-1];

		        n = (num[i-1]-'0')*10 + num[i]-'0';



				if (n <= 26 && num[i-1] != '0')

					a[i] += a[i-2];

			}

			

		}

		cout << a[size-1] << endl;

	}



	return 0;

}



좋은 웹페이지 즐겨찾기