DP14 [Java] BOJ 9465번 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 처음 스티커를 선택하는 경우는 각각의 스티커를 가져오게 했습니다. 그다음으로 이전 스티커를 선택했다면 이전에 뗄 수 있는 스티커까지 즉, 만약 현재 스티커의 i가 0이라면 memo[1][i - 1]을 i가 1이라면 memo[0][i - 1]의 값을 가져오게 했습니다. 마지막으로 이전 스티커를 선택하지 않는 경우에는 그 이전까지 뗄 수 있는 스티커까지 즉, memo[0][j - 2], memo[0][j - 1] 중 큰 값을 가져와 이전 스티커를 선.. 2021. 4. 21. [Java] BOJ 1010번 다리 놓기 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 예를들어 N = 2, M = 5이고 i = 1, j = 1이라면 왼쪽에 한개, 오른쪽에 한개의 사이트이므로 위 이미지와 같이 1개의 연결이 가능합니다. i = 1, j = 5라면 왼쪽에 1개 오른쪽에 5개의 사이트가 있으므로 위 이미지와 같이 5가지 경우로 연결이 가능합니다. 이를 그래프로 표현하면 1 2 3 4 5 1 1 2 3 4 5 가 됩니다. 다음으로 i = 2이고 j = 1일 경우에는 위 그림과 같이 2개의 다리가 설.. 2021. 4. 16. [Java] BOJ 11052번 카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 만약 N = 4일 경우는 4장을 뽑았을 때 최대 값이므로 ① 1장을 이미 뽑았을때의 최대값 + P[3] (3장이 있는 카드팩의 비용) ② 2장을 이미 뽑았을때의 최대값 + P[2] (2장이 있는 카드팩의 비용) ③ 3장을 이미 뽑았을때의 최대값 + P[1] (1장이 있는 카드팩의 비용) ④ P[4] (4장이 있는 카드팩의 비용) 중 최대인 값을 선택하면 4장을 뽑았을때의 최대값을 만들 수 있습니다. 코드 import java.io.Bu.. 2021. 4. 15. [Java] BOJ 14501번 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 이때, 상담 완료까지의 기간이 N + 1일 까지라면 N번째날까지 처리가 가능하다는 것을 주의해야 합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int N, ans; public static int[] T = new int[16]; public static int[] P = new int[16]; public sta.. 2021. 4. 14. [Java] BOJ 1912번 연속합 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 매번 memo[i] = arr[i]로 초기화시켜주고 이전까지 저장한 값에서 현재 더할 수를 더한 결과와 초기화한 값을 비교하여 더 큰 값을 저장하게했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public s.. 2021. 4. 7. [Java] BOJ 2193번 이친수 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 DP를 이용해서 해결했습니다. 문제의 조건에서 이친수의 맨 앞에는 0이 올 수 없으므로 각 자릿수 별 이친수의 개수를 보면 한자리 = 1 → 1개 두자리 = 10 → 1개 세 자리 = 100, 101 → 2개 네 자리 = 1000, 1001, 1010 → 3개 다섯 자리 = 10000 10001 10010 10100 10101 →5개 ... N자리 = N - 1자리의 개수 + N - 2자리의 개수가 됩니다. 코드 import java.io.Buf.. 2021. 4. 1. 이전 1 2 3 다음