난 출력이 순서대로 나와야 하기에 인접행렬을 인덱스로 검색하면 자동으로 순서가 되므로 인접행렬을 씀
인접리스트를 쓴 다른사람들은 sort 함
소스코드
#include<iostream>
#include<queue>
using namespace std;
int v, e, s, map[1001][1001], check[1001];
void dfs(int now){
check[now] = true;
cout << now << " ";
for (int i = 1; i < v + 1; i++){
if (!check[i] && map[now][i])
dfs(i);
}
}
int main(void){
cin >> v >> e >> s;
int a, b;
for (int i = 0; i < e; i++){
cin >> a >> b;
map[a][b] = map[b][a] = 1;
}
dfs(s);
for (int i = 0; i < v + 1; i++)
check[i] = false;
cout << "\n";
queue<int> q;
q.push(s);
check[s] = true;
while (!q.empty()){
int now = q.front();
q.pop();
cout << now << " ";
for (int i = 1; i < v + 1; i++){
if (!check[i] && map[now][i]){
q.push(i);
check[i] = true;
}
}
}
cout << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
숫자 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)에 있음]