Dynamic Programming(23)
-
[BOJ 11985] 오렌지 출하
https://www.acmicpc.net/problem/11985 11985번: 오렌지 출하 첫째 줄에 오렌지의 개수 N (1 ≤ N ≤ 20,000), 한 상자에 넣을 수 있는 오렌지 개수의 최댓값 M (1 ≤ M ≤ 1,000, M ≤ N), 상자를 포장하는 비용 K (0 ≤ k ≤ 1,000,000,000)가 주어진다. 둘째 줄부터 N개의 www.acmicpc.net 개수 - 문제 요약 Juicy Orange Industry(JOI)는 맛있는 오렌지를 포장해서 출하하는 것이 주된 업무인 회사이다. JOI사에서는 수집한 N개의 오렌지를 상자에 넣어서 출하한다. 먼저, 오렌지는 공장에 있는 컨베이어 벨트 위에 나란히 놓아야 한다. 컨베이어 벨트 위에 놓여져있는 오렌지는 앞에서부터 순서대로 1부터 N까..
2023.05.07 -
[BOJ 2237] 수열 축소
https://www.acmicpc.net/problem/2237 2237번: 수열 축소 N개의 양수로 이루어진 수열 {A[1], A[2], …, A[N]}이 있다. 이 수열에 A[i]에서 A[i+1]을 빼는 축소 연산을 적용하려 한다. 축소 연산은 CON이라는 함수로 나타낼 수 있으며, CON(A, i)를 수행하면 {A[1], A[2], www.acmicpc.net - 문제 요약 N개의 양수로 이루어진 수열 {A[1], A[2], …, A[N]}이 있다. 이 수열에 A[i]에서 A[i+1]을 빼는 축소 연산을 적용하려 한다. 축소 연산은 CON이라는 함수로 나타낼 수 있으며, CON(A, i)를 수행하면 {A[1], A[2], …, A[i-1], A[i] - A[i+1], A[i+2], …, A[N]}..
2023.05.06 -
[BOJ 8984] 막대기
https://www.acmicpc.net/problem/8984 8984번: 막대기 첫 줄에는 막대기의 개수와 수평선 사이의 간격을 나타내는 두 개의 정수 N과 L이 주어진다. 여기서 N은 1 이상 100,000 이하이고, L은 1 이상 1,000,000 이하이다. 그 다음 N 개의 줄에는 각 줄마다 막대 www.acmicpc.net - 문제 요약 다양한 길이의 막대기를 가지고 즐길 수 있는 게임이 있다. 게임을 시작하기 전에 간격이 L인 두 개의 평행한 수평선을 책상 위에 긋고, 막대기의 양 끝이 각 수평선에 하나씩 위치하도록 놓는다. 여러 개의 막대기 끝이 수평선 위의 한 점에서 만날 수는 있지만, 두 막대기가 완전히 겹쳐져 있는 경우는 없다. 놓여 있는 각 막대기는 (t, d)로 표현된다. 여기서..
2023.05.05 -
[BOJ 1398] 동전 문제
https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net - 문제 요약 구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000... 즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25×100K인 동전이 있는 것이다. 구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사 가려고 한다. 초콜릿의 가격이 주어졌을 때, 이를 구매하기 위해 필요한 ..
2023.05.02 -
[BOJ 20188] 등산 마니아
https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net - 문제 요약 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오두막에서도 다른 모든 오두막으로 하나 이상의 오솔길을 따라 이동하는 것이 가능하다. 오두막들은 1번부터 N번까지 번호가 붙어 있으며, 1번 오두막이 산 정상에 있다. 1번 오두막에서 다른..
2023.04.24 -
[BOJ 13209] 검역소
https://www.acmicpc.net/problem/13209 13209번: 검역소 3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사 www.acmicpc.net - 문제 요약 한 나라에는 N 개의 도시들이 있고, 두 도시 사이를 연결하는 길이 N − 1개 있다. 어느 두 도시도 오직 하나의 경로로만 서로 통행할 수 있게 되어 있고, 이곳에는 몇 년에 한 번씩 큰 전염병이 돈다. 정부에서는 이 문제를 해결하기 위해 N −1 개의 길들 중 K 개의 길에 검역소를 운영하려고 한다. 또한, 어떤 사람이 전염병에 감염될 경우를 대비하여 치료제를 비축해 두려..
2023.04.22