알고리즘37 백준 14445 케이크(?) 자르기 C++ 해설애드혹 문제라서 발상을 떠올리는게 쉽지 않았다.케이크의 높이가 명시되어 있지 않으므로, 케이크의 높이가 케이크 윗면의 가로 길이랑 다를 수 있음을 인지해야 한다. 케이크의 높이가 다르기에 자르는 방식에 따라 케이크의 옆면에 묻은 생크림이 달라질 수 있다.이에 따라, 케이크의 윗면과 옆면을 어떻게 배분해야 하는가에서 난관이 생긴다. 그러나 이는 원을 n등분 할 때를 떠올리면 해결된다. 윗면이 원인 원통형 기둥을 생각해보자. 원의 중심을 따라 n등분하면 옆면을 쉽게 배분할 수 있다. 그래서 이 문제에서는 모든 절취선이 정사각형의 중심을 통해서 n등분이 되면 높이, 즉 옆면을 신경쓰지 않고 케이크를 수직으로 자르면 된다. 이제, 케이크의 윗면만 n등분해서 배분하면 되는 문제로 바뀐다. n = 1의 경우,.. 2024. 8. 2. 백준 12869 뮤탈리스크 간단한 해설 뮤탈 타다당을 얼마나 효율적으로 쏠 지 계산하는 문제 n이 최대 3이고 최대 체력이 60이니까 단순한 bfs로 해결할 수도 있다고 생각할 수 있으나, 방문 처리를 안해주면 방문한 곳을 재방문해서 시간초과가 일어날 수 있음을 명시해야 한다. 재방문처리를 생각하면 문제 유형은 dp+bfs라 생각해도 된다. 코드를 좀 더 간결하게 짤 수도 있었지만 그냥 문제풀이가 목적이므로 같은 부분을 반복해서 복붙했다. 헷갈리지 않도록 주석 쓴게 포인트답#include #include #include #include using namespace std;int dp[61][61][61];int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n; .. 2024. 7. 29. 백준 28140 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕! C++ 단순한 해설문자열의 길이가 N이고 쿼리의 개수가 Q인데, 둘 다 최대치가 백만이다. 단순 탐색으로는 제 시간에 풀 수 없다. 단순히 이분탐색을 여러번 하면 된다.답#include #include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); string str; int n,q; cin>>n>>q>>str; deque r; deque b; for(int i=0;i>L>>R; int ansA=lower_bound(r.begin(),r.end(),L)-r.begin(); if(ansA==r.size()){ .. 2024. 7. 23. 백준 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. 이전 1 2 3 4 5 6 7 다음
