boj, 백준) 11779. 최소비용 구하기2 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 문제 개요 간선이 주어지고 출발지, 도착지의 정점 번호가 주어질 때, 출발지, 도착지까지의 최단거리, 경로를 구하는 프로그램을 작성하시오. 3. 문제 힌트 (1) 인접 리스트로 나타낼 것. -> 한 정점에서 다른 정점까지의 간선이 1개라면 행렬로 나타내어도 괜찮다. 그런데 한 정점에서 다른 정점까지 간선이 여러 개 있을 수 있으니 인접 리스트로 나타내어야 한..
boj, 백준) 5022. 연결(C/C++)
1. 문제 링크 www.acmicpc.net/problem/5022 5022번: 연결 A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다. www.acmicpc.net 2. 문제 개요 전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을수록 좋다. 크기가 N x M인 비어있는 회로판에서 두 점 A1, A2, 그리고 B1, B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안 된다. 이 경우에 필요한 전선의 길이의 최솟값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다. 3. 문제 힌트 (1) (A1--A2) (B1--B2..
boj, 백준) 20058. 마법사 상어와 파이어스톰(C/C++)
1. 문제 링크 www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 2. 문제 개요 크기가 2^N x 2^N인 격자로 나눠진 얼음판이 있다. A[r][c] (행 : r, 열 : c)의 값은 얼음의 양을 나타낸다. 파이어스톰을 시전하려면 시전 할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2^L x 2^L의 크기로 나누고 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸을 기준으로 3개 이상의 얼음과 인접..
boj, 백준) 20057. 마법사 상어와 토네이도 ( C/C++)
1. 문제 링크 www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 2. 문제 개요 토네이도를 크기가 N x N인 격자로 나누어진 모래밭에서 연습하려고 한다. 각 격자에는 모래가 일정량 쌓여있고, 토네이도가 오면 주변으로 흩날리게 된다. 모래밭의 바깥으로 나간 모래의 총량을 구하는 프로그램을 작성하시오. 3. 문제 힌트 (1) 토네이도의 경로 - 1,1 / 2,2 / 3,3/ ... / n-1,n-1,n-1칸 이동하는 것을 볼 수..
boj, 백준) 20056. 마법사 상어와 파이어볼 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 2. 문제 개요 마법사 상어가 크기가 N x N인 격자에 파이어볼 M개를 발사한다. 가장 처음 파이어볼은 각자 위치에서 이동을 대기하고있다... 등등 문제가 길고 복잡해서 문제는 다 안다고 가정하겠습니다. 여튼, 마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자. 3. 문제 힌트 (1) 파이어볼을 어떻게 가지고 있을 것인지 생각..
boj, 백준) 5719. 거의 최단 경로( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 2. 문제 개요 주어진 도로의 거의 최단경로를 구하자. 거의 최단경로는 최단경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 3. 문제 힌트 최단경로를 제거해야 하기 때문에, dijkstra 최단경로 알고리즘을 1회 실행하자. 이때, O(n^2)가 아닌 log형태인 우선순위 큐를 사용해야 함. (시간 ..