본문 바로가기
🔮 투 포인터 문제 모음집 [백준] 2003번: 수들의 합 (🥈 실버 3티어) [백준] 1806번: 부분합 (🥇골드 4티어 ) [백준] 1644번: 소수의 연속합 (🥇 골드 3티어) 2021. 9. 30.
[백준] 2003번: 수들의 합2 / C++ ✏️ 문제 링크 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net ✏️ 문제 설명 (더보기 클릭 👆🏻) 더보기 ✏️ 문제 코드 #include using namespace std; vector A; int main(){ int N,n, M; cin>>N>>M; n=N; while(n--){ int a; cin>>a; A.push_back(a); } int l=0, r=0; long sum=0, ans=0;.. 2021. 9. 30.
🔮 최단거리(다익스트라, 벨만포드, 플로이드 와샬) 문제 모음집 [백준] 1753번: 최단경로 (🥇골드 5티어) ✅ [백준] 1504번: 특정한 최단경로 (🥇 골드 5티어) ✅ [백준] 1446번: 지름길 (🥈실버 1티어) ✅ [백준] 1916번: 최소비용 구하기 (🥇 골드 5티어) ✅ [백준] 5972번: 택배 배송 (🥇 골드 5티어) ✅ [백준] 14284번: 간선 이어가기2 (🥇 골드 5티어) ✅ [백준] 17396번: 백도어 (🥇 골드 5티어) ✅ [백준] 1238번: 파티 (🥇 골드 3티어) ✅ [백준] 1162번: 도로 포장 (🥇 골드 1티어) ✅ [백준] 13308번: 주유소 [백준] 9376번: 탈옥 [백준] 5719번: 거의 최단 경로 [백준] 1854번: K번째 최단경로 찾기 [백준] 1856번: 웜홀 [백준] 11657번: 타임머신 [백준] 386.. 2021. 9. 28.
[백준] 1162번: 도로포장 / C++ ✏️ 문제 링크 https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net ✏️ 문제 설명 (더보기 클릭 👆🏻) 더보기 ✏️ 문제 풀이 1. 도로와 비용 배열 이전에는 dist배열이 1차원으로 시작노드에서 모든 노드까지의 최소 경로를 구하는 방식이었다. 하지만 이번 문제에서는 1번노드에서 다른 노드로 가는데! 몇번 포장을 해서 가냐, 또 k번 포장해서 해당 노드를 갔을 때의 최소비용이 무엇인지 알 필요가 있다. 따라서 .. 2021. 9. 28.
[백준] 1238번: 파티 / C++ ✏️ 문제 링크 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ✏️ 문제 설명 (더보기 클릭 👆🏻) 더보기 ✏️ 문제 풀이 1. i번째 학생이 X마을에 도착하는 최단 시간을 구한다. 2. X마을에서 i번째 마을로 i번째 학생이 돌아오는 최단 시간을 구한다. 3. 1,2번의 결과 값을 더해 answer에 max값을 넣어준다. for(int i=1; iN>>M>>X; while(M--){ int a, b, c; ci.. 2021. 9. 28.
[백준] 17396번: 백도어 / C++ ✏️ 문제 링크 https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net ✏️ 문제 설명 (더보기 클릭 👆🏻) 더보기 ✏️ 문제 풀이 기본 다익스트라에 아주 약간 조건을 추가해주면 된다. 상대편에 시야가 보이는 경우만 피해가면 되기 때문에 다음과 같은 조건을 추가한다. e-1가 아닌 경우에만 해당하는 이유는 마지막 도착지는 상대편에게 보일 수 밖에 없으며 무조건 1이기 때문에 갈 수 있어야 한다. if(sight[nxt] ==.. 2021. 9. 27.
[백준] 14284번: 간선 이어가기2 / C++ ✏️ 문제 링크 https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net ✏️ 문제 설명 (더보기 클릭 👆🏻) 더보기 ✏️ 문제 풀이 2021.09.15 - [Algorithm 🧠/알고리듬(thm) 공부 🌱] - [백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐ [백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐ ✏️ 문제 링크 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫.. 2021. 9. 27.
[백준] 5972번: 택배 배송 / C++ ✏️ 문제 링크 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net ✏️ 문제 설명 (더보기 클릭 👆🏻) 더보기 ✏️ 문제 풀이 2021.09.15 - [Algorithm 🧠/알고리듬(thm) 공부 🌱] - [백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐ [백준] 1916: 최소비용 구하기/ 다익스트라 / C++ ⭐ ✏️ 문제 링크 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의.. 2021. 9. 27.
[백준] 1446번: 지름길 / C++ ✏️ 문제 링크 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net ✏️ 문제 설명 (더보기 클릭 👆🏻) 더보기 ✏️ 문제 코드 #include #define MAX 10001 #define INF 987654321 using namespace std; using pii=pair; vector vec[MAX]; vector dist(MAX, INF); int main(){ int N, D; cin>>N>>D; while(N--){ int.. 2021. 9. 27.
반응형

티스토리툴바