본문 바로가기

전체 글140

[백준] 2169 - 로봇 조종하기 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 로봇은 위쪽으로는 이동할 수 없다. 따라서, 1행에서는 왼쪽 -> 오른쪽으로만 이동이 가능하다. 2행부터는 해당 행의 위의 행에서 오는 방법 해당 열의 왼쪽 열에서 오는 방법 해당 열의 오른쪽 열에서 오는 방법 이 존재한다. 따라서 이 세 경우를 모두 구현하면 된다. #include #include using namespace std; .. 2022. 8. 9.
[백준] 1507 - 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 최단 경로에 포함된 간선의 합을 구하는 문제이다. 맨 처음에 플로이드-와샬 알고리즘을 한 번 돌려본다. 이때 갱신되는 가중치가 생기면 미리 구해놓은 표는 맞지 않으므로 -1을 출력한다. 표가 맞다면, 모든 간선을 순회하며 각 간선의 가중치를 0으로 만들고 임시 배열로 플로이드-와샬 알고리즘을 수행한다. 이때 임시 배열의 가중치와 원래 배열의 가중치가 다르면 꼭 필요한 간선이 되므로, 답에 더한.. 2022. 8. 9.
[백준] 1938 - 통나무 옮기기 https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 문제를 보자마자 bfs가 떠올랐다. 그런데 특이한 조건이 있다. B와 E는 모두 이어져있으며 항상 길이가 3이다. 또한 방향이 존재한다. 이 점을 보고 visit[i][j][k] = 통나무 3개 중 가장 왼쪽 위에 있는 통나무의 위치가 i, j이며 k 방향을 가졌을 때 방문 배열로 정의하였다. 코드를 먼저 보고 설명을 이어나가도록 하겠다. #include #include #.. 2022. 8. 4.
[백준] 2933 - 미네랄 https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net #include #include #include using namespace std; int n, m; char map[100][100]; int getLeft(int i) { for (int j = 0; j = 0; j--) {.. 2022. 8. 4.
[백준] 1949 - 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net 다음과 같이 dp배열을 정의하면 거의 끝난다. dp[i][j]는, j가 0이면 해당 마을을 우수마을로 선정하지 않았을 때, 서브트리의 최대 우수 마을 주민 수 합 j가 1이면 해당 마을을 우수마을로 선정하였을 때, 서브트리의 최대 우수 마을 주민 수 합 그래서 일반 마을은 적어도 하나의 우수 마을과 인접해야 하므로 하위 서브트리의 j가 0일때와 1일때를 각각 구해 조건에 맞게.. 2022. 8. 4.
[백준] 1948 - 임계경로 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 이전 포스트와 거의 유사한 문제이다. 딱히 간선을 제거한 후 다시 다익스트라를 돌릴 필요 없이 그냥 최단 경로에 포함된 간선의 수만 세어주면 된다. #include #include #include #include using namespace std; int n, m, s, d; int meetTime; vector v; vector rev; vector dis; void.. 2022. 8. 4.
[백준] 5719 - 거의 최단 경로 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 이 문제는 최단 경로를 찾고, 최단 경로에 포함된 모든 간선을 삭제하는 문제이다. 최단 경로를 찾는 것은 다익스트라 1번으로 해결할 수 있다. 하지만 최단 경로에 포함된 모든 간선을 삭제하는 것이 약간 까다로웠다. 본인은 bfs, dfs 방법 모두 사용해 보았다. 핵심은 같은데, 바로 역추적이다. 도착점부터 역으로 출발해 해당 경로가 최단 경로이면 모두 삭제하는 방식.. 2022. 8. 4.
[백준] 10217 - KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 기존 다익스트라에서 최대로 갈 수 있는 가중치 정보와 그때 필요한 소요시간이 추가된 문제이다. 따라서 가중치가 2개(비용, 시간)라 볼 수 있다. 핵심은 비용이 최소로 되는 경로를 선택해도 시간이 최소가 아닐 수 있다는 것이다. 그래서 dp를 사용하게 되었다. dp[i][j] = i번 정점을 탐색하고, j만큼의 비용이 들었을 때 최소로 걸리는 시간 으로 배열을.. 2022. 8. 4.
[백준] 13334 - 철로 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 스위핑 문제의 대표적인 예다. 먼저 수열을 도착 지점 오름차순으로 정렬한다. 이렇게 정렬하면 우선순위 큐를 이용해 스위핑 알고리즘을 적용할 수 있다. 현재 해당하는 선분이 조건에 맞으면, 시작점을 우선순위 큐(최소 힙)에 삽입한다. 그래야 현재 선분의 도착점과 우선순위 큐의 top을 비교해 조건에 맞는지 검사할 수 있다. 이런 검사가 모두 끝나면.. 2022. 8. 4.

티스토리툴바