BOJ 2011 암호코드

문제출처 : https://www.acmicpc.net/problem/2011

1. 문제요약

- 알파벳 A ~ Z를 숫자 1 ~ 26에 대응 하여 암호를 만듦

- 25114 라는 암호를 만들었을 때, 해석 되는 가짓수는?

- 암호의 길이 N

- 1 <= N <= 5,000

2. 접근방법

- 길이가 n일 때, i 번째 숫자 까지 해석되는 경우의 수를 d[i]

- 최대 두 글자가 합쳐 질 수 있으므로

  d[i] = d[i-1] + d[i-2]

- 단, 0이 포함되어 있거나, 26을 넘어가는 숫자는 제외

- 01 인 경우, 숫자 0은 해석할 수 없으므로 d[1] = 0

- 10 인 경우, 숫자 1은 해석할 수 있으므로 d[1] = 1

                 숫자 0은 해석할 수 없으므로 1과 0은 따로 해석할 수 없고, 10은 해석 가능하므로 d[2] = 1

- 45 인 경우, 숫자 4, 5는 따로 해석 가능하지만, 45는 해석 할 수 없음. d[1] = 1, d[2] = 1

- 즉, 한 자릿수는 0 이외면 d[i] += d[i-1]

       두 자릿수는 10이상 26 이하면 d[i] += d[i-2]

3. 시간복잡도

- n

4. 회고

- 아에 생각을 잘못함...

-                   0 0 0 0 0

                   /           ＼

          0 | 0 0 0         0 0 | 0 0 0

- 이런식으로 나눠서 제일 마지막에 

  1개가 남고 0이 아니면 return 1

  2개가 남고 0이상 27 이하 이면 return 2

                 X0 인 경우 return 1

                 0X 인 경우 return 0

                 27 이상 return 0

- 이렇게 나눠서 생각했음

  너무 복잡하고 3333333 인경우 못골라냄...

- long long 은 약 18자릿수 까지 밖에 저장 못함...

- 5000 자릿수는 문자열로 받아야 함

  string 숫자를 int 숫자로 변환은 c[0] - '0'

- 넘 소스코드 좀 보자

- 난 n[i]와 d[i]의 인덱스를 같이 쓸려고 했는데

  같이 쓰면 d[1]일때 문자 2개의 경우의 수를 판단해야 되서 line 15와 같이 삽입했는데 그러지 말고

  d[n] : 길이 n번째 까지 만들 수 있는 암호의 수 라고 하면

  d[1]이 a[0]로 만들 수 있는 암호의 수가 되어서 line 15를 쓸 필요가 없었네

소스코드 : 맞은 소스

#include<iostream>
#include<string>
using namespace std;

#define div 1000000

string n;
int d[5001], ten, one;

int main(void){
	cin >> n;
	ten = n[0] - '0';
	one = n[1] - '0';
	if(ten != 0) d[0] = 1;
	if(9 < 10 * ten + one && 10 * ten + one < 27) d[-1] = 1;
	for(int i = 1; i < n.size(); i++){
		ten = n[i-1] - '0';
		one = n[i] - '0';
		if(one > 0) d[i] += d[i-1];
		if(9 < 10 * ten + one && 10 * ten + one < 27)
			d[i] += d[i-2];
		d[i] %= div;
	}
	cout << d[n.size() - 1] << "\n";
	return 0;
}

소스코드 : 틀린 소스

#include<iostream>
using namespace std;

#define div 1000000

int n, c[5001];
long long dp[501][501];

long long go(int s, int d){
    // 한자리가 남았을 경우
	if (d - s == 0){
        // 0 이 아니면
		if (0 < c[s]) return 1;
        // 0 이면
		else return 0;
	}
    // 두자리가 남았을 경우
	if (d - s == 1){
		if (0 < c[s])
			if (0 < c[d])
                // 둘다 0이 아니고 두자릿수가 27 미만인 경우
				if (10 * c[s] + c[d]) return 2;
				else return 0;
            // 십의 자리는 0이 아니고 1의 자리만 0인 경우
			else
                // 27 미만인 경우
				if (10 * c[s] < 27) return 1;
				else return 0;
		else return 0;
	}

	if (dp[s][d]) return dp[s][d];

	if (0 < c[s])
		dp[s][d] += go(s + 1, d);
	if (0 < c[s] * 10 + c[s + 1] && c[s] * 10 + c[s + 1] < 27)
		dp[s][d] += go(s + 2, d);
	dp[s][d] %= div;

	return dp[s][d];
}

int main(void){
	cin >> n;
	int cnt = 0, temp = n;
	while (temp){
		temp /= 10;
		cnt++;
	}
	for (int i = cnt; i > 0; i--){
		c[i] = n % 10;
		n /= 10;
	}
	cout << go(1, cnt) << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]