[BOJ] 2011 암호코드

 

2011번: 암호코드

 

 

한번 확인해보세요
1. 처음에 0~ 의입력을 정상적으로 받는지
ex) 
0 -> 0
011 -> 0
0101 -> 0 등등

2. 중간에 0이 있을때 그앞 두자리를 고려하는지
ex)
1203 -> 1 인데
세번쩨 0을 고려하지않고 12를 먼저 고르고 그다음 0을 보고 불가능으로 0을 출력하진 않았는지

3. 26이하와 27이상을 잘 구분하였는지
ex)
2626 -> 4
2727 -> 1

원래 내가 하려던 방법으로 계속 진행해보려 했으나 2번 반례에서 실패..

 

1203

DP[0] = A

DP[1] = AB, L

DP[2] = AT

DP[3] = ATC ---->1가지

 

내가 작성한 코드

#include <iostream>
#include <string>
#define MAXN 5000
using namespace std;

string N;
long long int DP[MAXN + 1];
void input() {
	cin >> N;
}

long long int solve() {
	if (stoi(N.substr(0, 1)) < 1)
		return 0;
	if (N.length() == 2 && stoi(N.substr(0, 2)) > 26)
		return 0;
	DP[0] = 1;
	DP[1] = stoi(N.substr(0, 2)) <= 26 && stoi(N.substr(0, 2)) >= 10 ? 2 : 1;

	for (int i = 2; i < N.length(); i++) {
		string cur1 = N.substr(i, 1);
		string cur2 = N.substr(i - 1, 2);

		if (stoi(cur1) < 1 && stoi(cur2) < 1) 
			return 0;

		
		DP[i] =
			stoi(cur2) <= 26 && stoi(cur2) >=10? (DP[i - 2] + DP[i - 1]) % 1000000 : DP[i - 1] % 1000000;
		
	}
	return DP[N.length() - 1] ;
}
int main() {
	input();
	cout << solve() << endl;
}

1203  ---->3

DP[0] = A

DP[1] = AB, L

DP[2] = DP[0] + DP[1]

i-2에서 (i-1 : i)가 두자리 수이고 26이하의 값인지 고려하는 것은 맞으나 i-1에서 i의 값이 0일 경우를 생각안해줌

 

정답 코드

#include <iostream>

#include <string>

using namespace std;

 

const int MAX = 5000 + 1;

const int MOD = 1000000;

int len;

int arr[MAX];

int cache[MAX];

 

int password(void)

{

        cache[0] = 1; //0

        for (int i = 1; i <= len; i++)

        {

//A~I로 인지하였을 경우

               if (arr[i] >= 1 && arr[i] <= 9)

                       cache[i] = (cache[i - 1] + cache[i]) % MOD;

               if (i == 1)

                       continue;

               //J~Z로 인지하였을 경우

               int temp = arr[i] + arr[i - 1] * 10;

               if (10 <= temp && temp <= 26)

                       cache[i] = (cache[i - 2] + cache[i]) % MOD;

        }

        return cache[len];

}

 

int main(void)

{

        string s;

        cin >> s;

        len = s.length();

        if (len >= MAX)

               exit(-1);

 

        for (int i = 1; i <= len; i++)

               arr[i] = s[i - 1] - '0';

        if (len == 1 && s[0] == 0) //중요

               cout << 0 << endl;

        else

               cout << password()<< endl;

        return 0;

}



출처: https://jaimemin.tistory.com/459 [꾸준함]

 

 

 

 

글 읽기 - 혹시 반례 못찾으시겠는분