https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 2차원 배열 cache에, cache[index][train] = "index위치부터 train개의 소형 기관차를 배치할 수 있을 때, 최대 손님 수"를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다 코드 #include #include #include using namespace std; int n; int people[50005]; int psum[50005]; int cache[5..

https://www.acmicpc.net/problem/23032 23032번: 서프라이즈~ 쿠기는 가톨릭대학교 컴퓨터정보공학부 학부장이다. 곧 다가오는 시험 기간에 학생들에게 힘을 주고자 간식 행사에 안심 스테이크를 주려고 한다. 컴퓨터정보공학부에는 N명의 학생이 있는데, www.acmicpc.net 1~n-1 지점을 모두 중간지점으로 해보면서, 해당 중간지점을 기준으로 왼쪽(left ~ 중간지점) 구역의 합과 오른쪽(중간지점+1 ~ right) 구역의 합의 차이를 작게 만들도록 left와 right를 움직여 가며 문제를 해결했다. 코드 #include #include #include using namespace std; int n; int weight[2005]; int psum[2005]; int..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 각 별들 사이 길이를 재서, 간선을 만들고, 해당 간선을 통해 최소 스패닝 트리를 만들어 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n; vector star; vector edge; //(별 사이 거리,별1,별2); int parent[105]; int rank_size[105]; void p..

https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 각 지점을 출발점으로 한 번씩 다익스트라를 수행하는데, 이때 다익스트라를 수행하는 우선순위 큐에, 처음에 어디로 이동했는지에 대한 정보도 함께 넣어서 출발지에서 어떠한 지점으로 최단거리에 왔을 때 처음에 어디로 이동했는지도 알 수 있도록 했다. 코드 #include #include #include #include #include using namespace std; int n, m; vector short..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 3차원 배열 cache에 cache[누를 순서][현재 왼발 위치][현재 오른발 위치] = "지금부터 끝까지 누르는데 최소로 드는 힘"을 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n; vector order; int cache[100005]..

https://www.acmicpc.net/problem/18877 18877번: Social Distancing The first line of input contains $N$ and $M$. The next $M$ lines each describe an interval in terms of two integers $a$ and $b$, where $0 \leq a \leq b \leq 10^{18}$. No two intervals overlap or touch at their endpoints. A cow standing on the endpoint of a www.acmicpc.net 소들 사이 거리를 특정값 이상으로 해서 주어진 범위에 모두 배치할 수 있는지 확인하는 이분 탐색을 수행하여, ..