알고리즘55 백준 15824 너 봄에는 캡사이신이 맛있단다 C++ small은 쉽게 맞았는데, large는 상당히 헤매었다.smallO(N^2)로 단순히 문제를 풀었더니 50점이 나왔었다i 와 j 루프로, (i-j) * 2^x로 구하였더니 O(N^2)로 Large에서는 시간초과가 나왔다.#include #include #include #define ll long long#define MOD 1000000007LLusing namespace std;ll table[300001];ll makeTable(ll n){ ll& ret=table[n]; if(ret!=0) return ret; if(n==0) return ret=1; if(n&(1>n; vector v(n); for(int i=0;i>v[i]; } sort(v.begin.. 2024. 5. 9. 백준 16437 양 구출 작전 C++ 단순한 dfs문제인데 캐싱을 생각해야한다.트리 재귀(dp)라고는 하는데, 나는 별 생각 없이 잘풀었다. graph 벡터로 그래프를 만들어내었고, table 벡터로 캐싱을 하였다.답#include #include #include #include #define ll long longusing namespace std;vector> graph;vector> table;ll dfs(int src){ if(graph[src].size()==0){ return table[src].first; } ll tmp=0; for(int i=0;i0){ table[src].first+=tmp-table[src].second; } return table[src].firs.. 2024. 5. 2. 백준 24391 귀찮은 해강이 C++ 단순한 유니온 파인드 문제, 문제를 잘 읽어보면, 다익스트라도 아니라는 것을 알 수 있다.단순하게 부모가 같으면 된다. 그리고 n이 10^5이므로, union by rank를 굳이 구현할 필요도 없어서 엄청 쉬운 문제이다.답#include #include #include using namespace std;int parent[100001];int n,m;int findParent(int vertex){ if(parent[vertex]!=vertex) parent[vertex]=findParent(parent[vertex]); return parent[vertex];}int main(){ cin.tie(0); ios_base::sync_with_stdio(0); cin>>n>>m.. 2024. 4. 29. 백준 19941 햄버거 분배 C++ 문제 보고 그냥 단순하게 왼쪽부터 차례대로 전부 탐색 시간제한이 0.5초이고, n이 20000개, k가 10이다. 최소한 20000 * 10하면 이십만번 탐색하면 0.5초도 안걸린다고 생각해서 전부 탐색해도 된다. 답 #include #include #include using namespace std; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,k; cin>>n>>k; string a; cin>>a; vector visited(n,false); int ans=0; for(int i=0;i 2024. 4. 21. 백준 17406 배열 돌리기 4 C++ 단순히 손이 많이 가는 백트래킹 배열을 돌릴 순서를 정하고, 배열을 돌리면 된다. 간단한 해설 배열을 돌릴 순서를 정하는 법 단순히 백트래킹 기법을 이용한다. 배열을 돌리는 법 c(거리)에 따라서 모든 거리를 동적으로 돌린다. (rotateArray 함수 부분) 만약 거리가 3이면 먼저 거리 1 회전, 그다음 거리 2 회전 그리고 마지막으로 거리 3 회전을 하면 된다. 나머지 디테일은 전부 생구현 내 아이디어 스케치 답 #include #include #include #include #include using namespace std; vector v(50,vector(50)); deque picker; int n,m,k,r,c,s; int ans=987654321; void rotateArray(vec.. 2024. 4. 16. 백준 22115 창영이와 커피 C++ 단순한 배낭 문제 반례 1 0 1답 : 0 답 #include #include #include using namespace std; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,k; cin>>n>>k; vector v(n); for(int i=0;i>v[i]; } vector dp(n+1,vector(k+1,200)); dp[0][0]=0; for(int i=1;i 2024. 4. 16. 이전 1 ··· 5 6 7 8 9 10 다음
