알고리즘/백준14 백준 1939 중량제한 C++ 간단한 해설시작점부터 도착점까지 최대 중량 제한을 bfs로 찾으면 된다.같은 지점을 여러 번 방문할 수 있어서 int인 방문 배열로 체크하는게 포인트간단한 반례6 121 2 71 3 81 4 71 6 92 3 73 4 73 5 74 5 74 6 73 6 71 3 115 6 126 3ans: 9 답 #include #include #include #include using namespace std;int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int n,m; cin>>n>>m; vector>> v(n+1,vector>()); // weight, idx for(int i=0;i>a>>b>>c; v[a].pus.. 2024. 8. 19. 백준 20055 컨베이어 벨트 위의 로봇 C++ 간단한 해설지문이 거지같아서 문제가 어렵다고 느낀 문제 1번 위치에서 로봇을 올리고, N번 위치에 로봇이 도착하면 로봇을 무조건 내린다.(내릴 때, 내구도는 소모하지 않음) 이하의 스크린샷에 담긴 모든 과정의 사이클이 돌아야 한 단계이다.(서식오류로 12134로 된 듯하다.) 다음의 링크를 통해 개선된 지문을 확인할 수 있다. problem-solve-hub/백준/Gold/20055. 컨베이어 벨트 위의 로봇/이해를 위한 문제 수정본.md at main · cThis is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://github.com/BaekjoonHub/BaekjoonHub). - codesv.. 2024. 8. 18. 백준 14222 배열과 연산 C++ 해설1부터 n까지 빈자리 모두 채워넣기 1부터 빈자리 찾아넣는다고 해서 그리디라고는 한다는거같은데 그리디의 개념은 조금 약한거 같다.간단하게 풀기 가능답#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]; } sort(v.begin(),v.end()); vector visited(n,false); for(int i=0;i 2024. 8. 7. 백준 1781 컵라면 C++ 해설문제를 처음 보자마자 그리디 알고리즘인 것을 깨닫고 우선순위 큐를 사용하였다. n과 데드라인이 20만까지 나올 수 있으므로, n이 20만이고, 모든 숙제의 데드라인이 20만인 경우의 수를 생각해봐야 한다. 데드라인에 맞춰 가장 큰 컵라면의 수를 뽑을려 하면 시간초과에 걸린다. 그렇기에 반대로 생각해서 날짜를 정한다.제일 처음 날짜부터 차례대로 정해두고 가장 큰 컵라면의 수를 꺼내면 문제를 풀 수 있다. 이때, 데드라인때문에 삭제될 수 있는 값들은 우선순위 큐를 하나 더 이용해서 지우는 것이 포인트이다. 답 #include #include #include #include #define ll long longusing namespace std;int main(){ cin.tie(0); ios_.. 2024. 8. 3. 백준 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. 이전 1 2 3 다음
