본문 바로가기

전체 글

1016 에라토스테네스의 체를 이용하기 #include #include using namespace std; using ll = long long; bool sieve[1000010]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll S,L; cin>>S>>L; ll ans = 0; for(ll i = 2; i = 0 && sieve[i*i - S]) continue; for(ll j = i * i * (S/(i*i)); j = S) sieve[j - S] = true; } } for(ll i = 0; i 더보기
2213 값을 구한 후 그 값이 어떻게 나왔는지 추적을 해야 하는 문제 사회망서비스(SNS)문제와 매우 비슷하다. #include #include #include #include using namespace std; int N; int dp[10010][2]; vector v[10010]; int W[10010]; vector ansset; void dfs(int x,int par){ if(dp[x][0] != -1) return; dp[x][0] = 0; dp[x][1] = W[x]; for(int i:v[x]){ if(i==par) continue; dfs(i,x); dp[x][1] += dp[i][0]; dp[x][0] += max(dp[i][1],dp[i][0]); } return ; } void sol(.. 더보기
2533 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 1. 부모가 얼리어댑터가 아닐 때 : dp[부모][0] += dp[자식][1] 2. 부모가 얼리어댑터일 때 : dp[부모][1] += min(dp[자식][0],dp[자식][1]) #include #include #include using namespace std; int N; int dp[1000010][2]; vector v[1000010]; void dfs(int x,int par){ i.. 더보기
2110,2447 //2447 #include using namespace std; int k; char map[7000][7000]; void sol(int i,int j,int sz){ if(sz == 1){ map[i][j] = '*'; return; } int nsz = sz/3; for(int m = i; m >k; sol(0,0,k); for(int i = 0; i < k; i++){ for(int j = 0; j < k; j++){ if(map[i][j] != '*'.. 더보기
1450 로봇청소기 #include using namespace std; int N,M,r,c,d,ans,z; int map[51][51]; int dx [4] = {-1,0,1,0}; //N,W,S,E int dy [4] = {0,1,0,-1}; bool clean[51][51]; bool running = true; int getLeftDir(int d){ if(d == 1) return 0; if(d == 0) return 3; if(d == 3) return 2; if(d == 2) return 1; } int getBackDir(int d){ if(d == 1) return 3; if(d == 2) return 0; if(d == 3) return 1; if(d == 0) return 2; } int main(){.. 더보기
16888 루트 게임 각 턴에서 각 사람은 1보다 크거나 같은 완전제곱수 x를 하나 고르고, N에서 x를 뺀다. 정수는 0보다 작아질 수 없으며, 0을 만드는 사람이 게임을 이긴다. 두 사람이 모두 최적의 방법으로 게임을 했을 때, 이기는 사람이 누구인지 구하는 프로그램을 작성하시오. #include using namespace std; int T; bool dp[1000001]; int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>T; dp[0] = false; for(int i = 1; i N; if(dp[N]) cout 더보기
15877 https://www.acmicpc.net/problem/15877 15877번: Apples and Bananas The numbers of apples (a) and bananas (b), separated with a space. (0 ≤ a, b ≤ 1,000) www.acmicpc.net game 과 dp 문제이다. #include using namespace std; int x, y; bool dp[1011][1011]; int main() { cin>>x>>y; dp[1][0] = true; dp[0][1] = true; dp[1][3] = true; dp[3][1] = true; for(int i = 2 ; i = 3 && !dp[i-1][j-3]) dp[i][j] = true; } } i.. 더보기
1068 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 부모 자식 관계만을 이용해서 해결하는 문제 삭제할 때 dfs를 이용해서 쭉 삭제함( p[x] = -2 ) 리프노드 : 어떤 노드를 부모로 하는 노드가 없으면 그 노드는 리프 노드이다. //1068 #include #include using namespace std; int n, ans; int p[51]; void dfs(int x){ p[x] = -2; // 삭제 for(int i = 0;.. 더보기

티스토리툴바