My life story

1. 문제 링크 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. � www.acmicpc.net 2. 문제 개요 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 두 행성을 x, y, z 좌표로 나타내고, 터널로 연결할 때 드는 비용은 min(|x2-x1|, |y2-y1|, |z2-z1|)로 정의한다. 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하자..

1. 문제 링크 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 2. 문제 개요 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을을 2개로 쪼개고, 각 마을의 집들은 다 연결되어있어야 한다. 길의 최소비용을 구해보자. 3. 문제 힌트 (1) 마을1개에서 모든 집들을 가장적은 비..

1. 문제 링크 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, �� www.acmicpc.net 2. 문제 개요 N개의 마을로 이루어진 나라가 있다. 1부터 N까지 번호가 붙어있다고 하자. 이 나라는 Tree구조로 이루어져 있다. 마을과 마을 사이를 잇는 N-1개의 길이 있으며 양방향 간선이다. (1) '우수 마을'로 선정된 마을 주민 수의 총합을 최대로 해야 한다. (2) 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우..

1. 문제 링크 https://www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려� www.acmicpc.net 2. 문제 개요 DNA 서열은 4개의 문자로 이루어진 문자열이다. (1) at와 gc는 가장 짧은 길이의 KOI 유전자이다. (2) 어떤 X가 KOI유전자라면, aXt, gXc도 KOI 유전자이다. (3) 어떤 X, Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다. 문제에서 주어진 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI유전자..

1. 문제 링크 https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소� www.acmicpc.net 2. 문제 개요 초라기는 각각 W명으로 구성된 특수 소대를 다수 출동시켜 모든 구역에 침투시킬 예정이다. 특수 소대를 배치하는 데는 여러 조건이 있다. 원타곤의 모든 구역을 커버하기 위해 침투시켜야 할 특수 소대의 최소 개수를 출력하는 프로그램을 만들자. 3. 문제 힌트 문제를 곰곰히 생각해보면 타일링 문제와 상당히 비슷함을 알 수 있..

1. 문제 링크 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마�� www.acmicpc.net 2. 문제 설명 DDR 게임을 하면서 발을 움직일 건데 가장 적은 에너지를 사용하여 움직일 때, 에너지의 최솟값을 찾자. 움직일 때 에너지 값은, 열에서 행으로 이동한다고 가정했을 때, 열 -> 행 0 1 2 3 4 0 1 2 2 2 2 1 0 1 3 4 3 2 0 3 1 3 4 3 0 4 3 1 3 4 0 3 4 3 1 이다. 3. 문제 힌트..