- 1) 방법은 해당 특정 숫자가 몇번째 인지 저장해서 한번 방문했던 숫자를 재 방문하면 해당 cnt를 리턴
num이 얼마나 커질지 모름....
- 2) 방법은 cnt에 num을 가지고 있음
배열의 크기는 최대 1000을 넘지 않지만
해당 숫자가 이전에 있었는지를 연산 후에 매번 확인해줘야함.
3. 시간복잡도
- 1)은 O(N) : 1,000
- 2)는 O(N^2) : 1,000,000
4. 회고
- 난 1)번 방법으로 풀긴했는데 음... 2)번 방법이 좀 더 확실할 것같다.
1)번은 배열 크기를 알 수가 없으므로
소스코드 : 1)번 방법
#include<iostream>
#include<vector>
using namespace std;
int p;
vector<int> a(300000, -1);
int cal(int num){
int result = 0;
while (num){
int temp = 1;
int mul = num % 10;
for (int i = 0; i < p; i++)
temp *= mul;
result += temp;
num /= 10;
}
return result;
}
int dfs(int num, int cnt){
if (a[num] != -1)
return a[num];
a[num] = cnt;
return dfs(cal(num), cnt + 1);
}
int main(void){
int temp;
cin >> temp >> p;
cout << dfs(temp, 0) << "\n";
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
#include<iostream>
#include<vector>
using namespace std;
int t, n;
vector<int> a;
vector<bool> check;
void dfs(int now){
check[now] = true;
if (!check[a[now]])
dfs(a[now]);
}
int main(void){
cin >> t;
while (t--){
cin >> n;
a = vector<int>(n + 1);
check = vector<bool>(n + 1, false);
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = 1; i <= n; i++)
if (!check[i]){
ans++;
dfs(i);
}
cout << ans << "\n";
}
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n, m, ans = 0, check[1001];
int main(void){
cin >> n >> m;
vector<vector<int> > g(n + 1);
int a, b;
for (int i = 0; i < m; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
queue<int> q;
for (int i = 1; i < n + 1; i++){
if (!check[i]){
ans++;
q.push(i);
check[i] = true;
while (!q.empty())
{
int now = q.front();
q.pop();
for (int j = 0; j < g[now].size(); j++){
if (!check[g[now][j]]){
q.push(g[now][j]);
check[g[now][j]] = true;
}
}
}
}
}
cout << ans << "\n";
return 0;
}
소스코드 : dfs
#include<iostream>
#include<vector>
using namespace std;
int n, m, ans, check[1001];
vector<vector<int> > g;
void dfs(int now){
check[now] = true;
for (int i = 0; i < g[now].size(); i++){
if (!check[g[now][i]])
dfs(g[now][i]);
}
}
int main(void){
cin >> n >> m;
g.resize(n + 1);
int a, b;
for (int i = 0; i < m; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i < n + 1; i++){
if (!check[i]){
ans++;
dfs(i);
}
}
cout << ans << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
난 출력이 순서대로 나와야 하기에 인접행렬을 인덱스로 검색하면 자동으로 순서가 되므로 인접행렬을 씀
인접리스트를 쓴 다른사람들은 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)에 있음]
- <소스 1>의 d 배열에는 나머지 값이 들어가 있어서 line 6에서 정상적으로 나머지값이 반환됨.
- <소스 2>의 d 배열에는 나머지 값이 들어가 있지 않아서 line 6에서 나머지 연산 전의 값이 반환됨.
<소스 2>의 line 6를 return d[sum][cnt] % div로 바꿔주면 정답
- <소스 2>의 line 11을 return d[sum][cnt] %= div로 바꿔주면 제일 빨리 수행됨
나머지 연산이 덧셈 때 마다들어가지 않기 때문에
- 예를 들어 div = 5일 때,
1 1 1 1 1 1 1 1 1
3 3 3
9 // <소스 1>은 9div5 = 4가 저장되고 / <소스 2>는 9가 저장됨
...
12 // <소스 1>과 <소스 2> 모두 합은 4 + 4 + 4 이지만
<소스 1>은 12div5 = 2가 <소스 2>는 12가 저장됨
메모이제이션할때 저장된 값을 리턴하면
<소스 1>은 2를 <소스 2> 는 12를 리턴하므로 틀린 값이 나옴
그래서 <소스 2>의 line 6를 return d[sum][cnt] % div로 바꿔주면 정답이 됨.
long long dp(int sum, int cnt){
if (cnt == 1)
return 1;
if (d[sum][cnt])
return d[sum][cnt];
for (int i = 0; i <= sum; i++){
d[sum][cnt] += dp(sum - i, cnt - 1);
d[sum][cnt] %= 1000000000;
}
return d[sum][cnt];
}
<소스 1>
long long dp(int sum, int cnt){
if (cnt == 1)
return 1;
if (d[sum][cnt])
return d[sum][cnt];
for (int i = 0; i <= sum; i++)
d[sum][cnt] += dp(sum - i, cnt - 1);
return d[sum][cnt] % 1000000000;
}
<소스 2>
소스코드 : Top-Down
#include<iostream>
using namespace std;
int n, k;
long long d[201][201];
long long dp(int sum, int cnt){
if (cnt == 1)
return 1;
if (d[sum][cnt])
return d[sum][cnt];
for (int i = 0; i <= sum; i++){
d[sum][cnt] += dp(sum - i, cnt - 1);
d[sum][cnt] %= 1000000000;
}
return d[sum][cnt];
}
int main(void){
cin >> n >> k;
cout << dp(n, k) << "\n";
return 0;
}
소스코드 : Bottom-Up
#include<iostream>
using namespace std;
int n, k;
long long d[201][201];
int main(void){
cin >> n >> k;
d[0][0] = 1;
for (int i = 1; i <= k; i++){
for (int j = 0; j <= n; j++){
for (int k = 0; k <= j; k++){
d[j][i] += d[j - k][i - 1];
d[j][i] %= 1000000000;
}
}
}
cout << d[n][k] << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
