Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 파이썬
- 기술면접
- 인턴십 면접
- 가장긴증가하는 부분수열
- 백준12738
- 카카오 인턴
- 백준12015
- 백준
- 카카오 서류전형
- 카카오 자기소개서
- Longest Increasing Subsequence
- 최장증가수열
- 단어수학
- LIS
- 백준11053
- Python
- 구간나누기
- 정상회담2
- LIS 알고리즘
- 카카오
- 2228
- DP
- 1670
- 2629
- 개발자 면접
- 카카오 인턴십
- 여름인턴십
- 카카오 면접
- 2482
- 알고리즘
Archives
- Today
- Total
프로그래밍에 대한 고찰 및 생각
[알고리즘][15][백준_2533] - 사회망 서비스 본문
이 문제에서 핵심이 되는 부분은
얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다.
이 부분이다.
이 말을 다르게 해석하면 결국 만약 자신이 일반인이라면 자신의 모든 친구들이 얼리어답터여야 함을 의미한다.
또한 만약 자신이 얼리어답터라면 자신의 친구가 일반인이던, 얼리어답터이던 중요하지 않다. 모두 가능하다.
정리하자면
얼리어답터 -> 얼리어답터 or 일반인
일반인 -> 얼리어답터
따라서 이것을 이용해 한정점에서 시작해 DFS로 순회하면서 위의 조건을 통해 최소의 얼리어답터 수를 구할 수 있을것이다.
만약 위와같은 트리로 전체적인 흐름을 파악해보자.
1번 정점부터 DFS를 수행한다고 할때 1번 정점에서 가능한 경우는 다음과 같이 두가지이다.
최종답은 두 경우중 얼리어답터가 더 적은 쪽이 될것이다.
이후 3번 정점을 통해 dp를 어떻게 설계해야하는지 살펴보자.
a) 1번이 얼리어답터 일때
자신이 얼리어답터이므로 3번은 얼리어답터이거나(좌측 그림) 일반인이다(우측 그림).
2번도 마찬가지로 그 두경우 모두 가능하다.
b) 1번이 일반인 일때
자신이 일반인이므로 3번은 반드시 얼리어답터여야한다.
2번도 마찬가지로 반드시 얼리어답터여야한다.
중복 확인
이제 a,b 두 경우에서 각각 3번이 얼리어답터일때를 보자.
3번의 부모에서 부모가 얼리어답터건 일반인이건 상관없이 3번 이후로 (6,7,8)번의 선택에는 영향을 주지못한다.
따라서 두 경우 이후 최소가 되는 얼리어답터 수는 같을 것이고 이를 처리해주지않으면 중복호출로 시간복잡도가 증가한다.
따라서 해당 정점번호 + (얼리어답터 or 일반인여부) 를 가지고 메모이제이션을 해주면 중복을 해결 할 수 있다.
d[i][0] = i 번째 정점이 일반인 일때 이후 정점들의 최소 얼리어답터 수
d[i][1] = i 번째 정점이 얼리어답터 일때 이후 정점들의 최소 얼리어답터 수
코드 (C++)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<vector<int> > v;
int vt[1000002];
int dp[1000002][2];
int run(int now, int type){
// now 정점을 type으로 했을때 최소값 리턴
// type = 0 : 일반인 / 1 : 얼리어답터
int next;
int r1;
int r2;
int total = 0;
int check = 0;
if(dp[now][type] != -1){
return dp[now][type];
}
for(int i=0;i<v[now].size();i++){ // 해당 정점에서 갈수있는 정점 모두 탐색
next = v[now][i];
r1 = 99999999;
r2 = 99999999;
if(vt[next] == -1){ // 다음노드가 아직 방문전이라면
vt[next] = 1;
if(type == 1){ // 현재 자신이 얼리어답터라면 다음 정점은 일반인이 될수있다.
r1 = run(next,0);
}
r2 = run(next, 1); // 현재 자신이 일반인이던 얼리어답터건 다음 정점은 얼리어답터가 될수있다.
vt[next] = -1;
}
if(!(r1 >= 99999999 && r2 >= 99999999)){
if(r1 < r2){ // 다음 정점이 일반인, 얼리어답터 중에 더 적은 얼리어답터를 만든 경우를 계속 합산
total = total + r1;
}
else{
total = total + r2;
}
}
}
if(type == 1){ // 최종 최소치에 자신이 얼리어답터라면 본인도 포함
total = total + 1;
}
dp[now][type] = total;
return total;
}
int main(){
int x,y;
cin >> n;
for(int i=0;i<=n;i++){
v.push_back(vector<int>());
vt[i] = -1;
for(int j=0;j<2;j++){
dp[i][j] = -1;
}
}
for(int i=0;i<n-1;i++){
cin >> x;
cin >> y;
v[x].push_back(y);
v[y].push_back(x);
}
vt[1] = 1;
int ans1, ans2;
ans1 = run(1,0);
for(int i=0;i<=n;i++){
vt[i] = -1;
}
vt[1] = 1;
ans2 = run(1,1);
cout << min(ans1,ans2);
}
'알고리즘 > 백준' 카테고리의 다른 글
[알고리즘][16][백준_7570] - 줄 세우기 (0) | 2021.09.23 |
---|---|
[알고리즘] [14][백준_11724] - 연결 요소의 개수 (0) | 2021.01.31 |
[알고리즘][13][백준_2618][c++] - 경찰차 (0) | 2021.01.29 |
[알고리즘][12][백준_7576][c++] - 토마토 (0) | 2021.01.23 |
[알고리즘][11][백준_1029][C언어] - 그림교환 (0) | 2020.03.04 |