a[집 갯수] = 단지 갯수
for(int i = 0; i < n*n + 1; i++){
for(int j = 0; j < a[i]; j++){
cout << i << "\n";
}
}
18.2.7
소스코드 수정 - num이 필요없잖아.. 벡터를 쓰는데
dfs만 수정함
소스코드 : dfs
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> house;
char map[25][25];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int dfs(int row, int col){
map[row][col] = '0';
int ret = 1, nr, nc;
for (int i = 0; i < 4; i++){
nr = row + dx[i];
nc = col + dy[i];
if (0 <= nr && nr < n && 0 <= nc && nc < n && map[nr][nc] == '1')
ret += dfs(nr, nc);
}
return ret;
}
int main(void){
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (map[i][j] == '1')
house.push_back(dfs(i, j));
sort(house.begin(), house.end());
cout << house.size() << "\n";
for (int i = 0; i < house.size(); i++)
cout << house.at(i) << "\n";
return 0;
}
소스코드 : bfs
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n, check[25][25];
char map[25][25];
vector<int> house;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int main(void){
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
queue<pair<int, int>> q;
int num = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
int cnt = 0;
if (!check[i][j] && map[i][j] == '1'){
q.push(make_pair(i, j));
check[i][j] = true;
num++; cnt++;
while (!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
int nx, ny;
for (int k = 0; k < 4; k++){
nx = x + dx[k];
ny = y + dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n
&& !check[nx][ny] && map[nx][ny] == '1'){
check[nx][ny] = true;
cnt++;
q.push(make_pair(nx, ny));
}
}
}
house.push_back(cnt);
}
}
}
sort(house.begin(), house.end());
cout << num << "\n";
for (int i = 0; i < house.size(); i++)
cout << house.at(i) << "\n";
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]
- 어떤 자연수 M => 세 자릿수 라면 100a + 10b + c => M + a + b + c = N 즉, M과 각 자릿수의 합을 분해합, M을 생성자, N을 분해합
- 1 <= N <= 1,000,000 인 자연수 N이 주어 졌을 때 가장 작은 생성자는?
2. 접근방법
- 생성자는 분해합을 넘을 수 없으므로 1 부터 N-1 까지의 모든 수를 다 해보자
- 좀 더 생각해보면 분해합 N이 만들어 질 수 있는 생성자의 최대 자릿수는 6자릿수
(생성자가 1,000,000 이면 분해합은 1,000,001 이므로 7 자릿수는 나올 수 없음)
각 자릿수의 최대 값은 9
즉, 생성자는 분해합 보다 54 이상 작을 수 없음.
N-54 부터 N-1 까지만 찾으면 됨.
가장 작은 수 부터 찾을 거니 처음 만나는 생성자가 최소값
3. 시간복잡도
- 두 가지 경우 모두 N
- 당연히 실제 시간은 전체 검색시 8ms / 55개 검사시 0ms
4. 회고
- 처음엔 다 했는데...
- 다른 사람의 소스 코드를 보고 깨달음
- 각 자릿수 합의 최대 범위
소스코드
#include<iostream>
using namespace std;
int main(void){
int n;
cin >> n;
for (int i = n - 54; i < n; i++){
int temp = i, sum = i;
while (temp){
sum += temp % 10;
temp /= 10;
}
if (sum == n){
cout << i << "\n";
return 0;
}
}
cout << '0' << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]