알고리즘/백준28 백준 30023 전구 상태 바꾸기 C++ 간단한 해설 알고리즘 분류에 그리디라고 되어있어서 계속 생각해봤지만, 그리디 풀이를 떠올릴 수 없었다. 그냥 브루트포스였다... 풀고나서 꽤 생각했는데 그리디 풀이가 안떠올랐다... 첫번째 색을 고정한다고는 하는데 이건 솔직히 그리디라 하기에는 억지다. n이 100,000이니까, 모든 색을 순회한다 하면 최악의 경우100,000 * 3 * 3이다.(세 가지 색에 연속된 세 전구를 바꾸는거)270만이면 1초 내에는 브루트포스로는 충분하다. 답 #include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n; string a; cin>>n>>a; ve.. 2024. 6. 18. 백준 2247 실질적 약수 C++ 간단한 해설어떤 자연수 x의 실질적 약수를 찾고, 그 자연수의 실질적 약수들의 합을 구한다. 이를 1부터 n까지 다 더한다. n이 2억이므로 웬만하면 시간복잡도 O(N)만에 끝내야 한다. n의 크기때문에 약수를 구하는 알고리즘으로는 이걸 해결할 수 없다. 그러면 이렇게 생각해보자. 어떤 자연수의 실질적 약수를 구하는 것이 아니라, 어떤 자연수의 실질적 약수의 합만 구하면 되는거다. 어떠한 자연수 x가 짝수라면 실질적 약수는 2가 포함되어 있을 것이다. 그러면 1부터 n까지 실질적 약수의 합에는2가 n/2-1 개 들어가 있다. (2의 실질적 약수의 합은 0이기 때문에 n/2-1이다.) 어떠한 자연수 x가 3의 배수라면 실질적 약수에는 3이 포함되어 있다. 그러면 1부터 n까지 실질적 약수의 합에는 3이 n.. 2024. 6. 12. 백준 1365 꼬인 전깃줄 C++ 간단한 해설?문제 양치기를 너무 많이해서 그런가 문제만 봐도 그냥 단순한 LIS임이 명백했다.(전깃줄 문제랑 비슷해보임)lower_bound를 통해 이분탐색으로 풀었다.답#include #include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,a; cin>>n; deque v; cin>>a; v.push_back(a); int ans=0; for(int i=1;i>a; auto it=lower_bound(v.begin(),v.end(),a); if(it==v.end()){ v.pu.. 2024. 5. 29. 백준 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. 이전 1 2 3 4 5 다음
