전체 글
-
[1197] 최소 스패닝 트리BOJ 2021. 9. 13. 18:20
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net MST 기본문제, 크루스칼이나 프림을 구현하면 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include #include #include..
-
[1753] 최단경로BOJ 2021. 9. 13. 18:17
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 입력은 방향그래프가 들어온다. 노드의 개수가 2만개여서 방향데이터를 인접리스트로 저장해야 한다. 가중치는 10이하의 자연수, 노드의 개수는 30만으로 힙을 이용한 다익스트라를 구현하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37..
-
[11508] 2+1 세일BOJ 2021. 9. 12. 16:40
https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net N개의 물건의 가격이 들어올때, 물건을 최대 3개까지 하나의 집합으로 분할이 가능하다. 3개의 원소로 이루어진 집합일때, 가장 싼 물건은 값을 지불하지 않아도 된다. 이때 지불할 비용을 최소화하는 문제다. answer = (전체 가격의 합) - (할인받은 가격의 합) 이다. 전체 가격의 합은 고정이므로 answer를 최소화하기 위해서, 할인받을 가격을 최대화해야한다. 그렇다면 가장 비싼..
-
[2011] 암호코드BOJ 2021. 9. 11. 15:35
https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 여러개의 경우로 나누어 점화식대로 구현해주면 된다. 아래 소스코드의 주석과 함께 보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include int dp[5001]; char s[5002]; ..
-
[16236] 아기 상어BOJ 2021. 9. 9. 20:39
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 탐색의 방법이 정형화된 bfs이고, 기준도 부등식 하나로 매우 간단하다. 주의할 점으로는, 초기에 아기상어가 위치한 곳에도 0(빈칸)으로 표시를 해두어야 한다. queue에 넣는것은 매칸마다 이동하는 것이 아닌, 아기상어가 하나의 물고기를 잡아먹을때마다 하나의 정점을 방문하는 것으로 생각한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..
-
[16933] 벽 부수고 이동하기 3BOJ 2021. 9. 9. 15:59
https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 벽 부수고 이동하기 2번 문제의 코드에서, 낮과 밤을 나타내는 불리언 변수만 추가해서 queue에 넣어주었다. 처음에는 다음 dist를 curDist+2-flag처럼, 낮일경우 거리1 추가, 밤일경우 거리2를 추가하는 형태로 구현하려 했지만 그렇게 할경우 bfs의 특성인 '먼저 도착하는 해가 최적해'라는 특성이 적용되지 않아 queue 전체가 빌때까지 탐색을 진..
-
[14442] 벽 부수고 이동하기 2BOJ 2021. 9. 9. 14:33
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이전의 '벽 부수고 이동하기' 문제와 유사하다. [2206] 벽 부수고 이동하기 :: Dizlet-Algorithm (tistory.com) [2206] 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동..
-
[17779] 게리맨더링 2BOJ 2021. 9. 9. 01:04
https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 입력은 2차원 배열, 이를 5개의 구역으로 쪼개고, 쪼개진 각 구역의 최대값-최소값을 최소화해야한다. 결국에는 균등하게 쪼개질수록 최적해에 가까워지는 문제라고 할 수 있다. 다만 쪼개는 형태가 직사각형 안에 45도 기울어진 직사각형을 그려진 형태이다. 직사각형의 경계와 그 안을 5번, 이 5번을 기준으로 좌상, 우상, 좌하, 우하의 4구역을 각각 1~4번으로 한다. 아래의 사진을 보자 4개의 꼭지점중 ..
-
[1013] ContactBOJ 2021. 9. 7. 22:00
https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 정규표현식을 사용하는 문제이다. 정규표현식은 (100+1+ | 01)+ 인데, 문제에 그대로 나와있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #include #include #include using namespace std; int t; int main(void) { scanf("%d", &t); while (t--) {..
-
[8980] 택배BOJ 2021. 9. 5. 18:15
https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 구간이 주어지고 이에대한 최적해를 greedy적 접근으로 해결하는 부분은 회의실배정 문제와 같다. 회의실배정 문제에서 회의실을 '빨리'끝나는 회의를 먼저 배정하듯, 이 문제도 도착이 빠른 택배를 먼저 배송한다. 회의실배정 문제는 회의실 개수의 최대화로, 회의를 배정할때마다 개수만 1 증가시켜주면 되지만 이 문제같은 경우 택배의 개수와, 트럭의 용량을 모두 고려하여 정답을 업데이..