6-6화이탱

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net DP와 누적합 문제로 풀어보면 좋을 문제인 듯 하다!! 점화식을 생각해내기 어려운 부분이 있어서 꼭 풀어보시면 좋겠다! 필자도 조만간 한번 더 풀어볼 예정이다 ,, ㅎㅎ 풀이 1.누적합을 이용하여 sum 배열에 넣어주고 2.dp 배열을 생성하여 숫자의 최솟값은 -32768이고 N은 100개까지 이루어지므로, dp[0][1~m]까지를 -3276800으로 초기화한다. 3. d..

https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 1명 - 0 2명 - 1 3명 - 2 4명 - 9 5명 - 44 이기에 (dp[i-1]+dp[i-2])*(i-1) 의 점화식이 성립된다! 해당 점화식과 1000000000으로 나눈 값을 출력하면 간단히 해결~! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws NumberFormat..

https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net DP 문제로 처음에 생각해내기 어려웠다.. 풀이 1. 리스트 배열을 만들어서 배열의 인덱스는 출발지, 리스트에는 도착지와 점수를 넣는다. ( 만일, 도착지가 출발지보다 작은 수라면 동쪽이동이기 때문에 스킵!) 2. dp 이차원배열을 생성하여 "new int[몇번째로 방문한 것인지=> m+1][도착지 번호=>n+1] = 점수" 를 저장할..