PS(Java)/백준

[PS] 백준 1912번 연속합

문제 예제 풀이 이 풀이를 참고하였다. dp[i] = dp[i-1] + arr[i] 가 누적합 식이라는 건 쉽게 도출했지만 이식은 0~i번째까지 적용되고, 문제에서 원하는 k~i번째 연속합은 dp[i]-dp[k-1]이다. '이 전까지의 연속합에서 현재 arr[i]를 더한 값과 현재 arr[i]를 비교하는데, 이 전까지의 연속합에서 arr[i]를 더한 값이 arr[i] 보다 작다면, 당연히 dp[i] = arr[i] 로 대체하는 것이 이득' -> 이부분을 전혀 떠올리지 못해서, 수열의 한자리(k) 씩 마다 k~i번째 연속합의 경우의 수를 모두 구하려다가 뭔가 이상한거 같아서 급히 풀이를 찾아보았는데 역시나 ㅠ 코드 .import java.io.IOException; import java.util.Scann..

[PS] 백준 11054번 가장 긴 바이토닉 부분 수열 - DP

문제 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 가장 긴 ~ 수열 문제에서는 다른 풀이를 참고해서 풀었기 때문에 배열의 길이를 n+1로 잡았었는데, 심화 문제를 풀려니 배열의[0]값을 쓰지 않는게 더 헷갈려서, n으로 잡고 코드를 바꿔서 풀었습니다. 10 1 5 2 1 4 3 4 5 2 1 위 예제 를 입력했을 때 dp값은 다음과 같이 저장되고, 두 배열을 더했을 때 최대값을 구하면 된다. dp[0][*] = {1, 2, 2, 1, 3, 3, 4, 5, 2, 1} dp[1][*] = {1, 5, 2, 1, 4, 3, 3..

[PS] 백준 11722번 가장 긴 감소하는 부분 수열 - DP

문제 예제 풀이 이전에 풀었던 문제 - [PS] 백준 11053번 가장 긴 증가하는 부분 수열 - DP 를 조금만 바꾸면 된다.' 코드 import java.io.IOException; import java.util.Scanner; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { Scanner in = new Scanner(System.in); int n = in.nextInt(); //수열의 크기 int[] arr = new int[n+1];//값 int[] dp = new int[n+1];//dp[탐색길이]에 가장 긴 수열의 길이 저장 for(int i=1; i

[PS] 백준 11055번 가장 큰 증가 부분 수열 - DP

문제 예제 풀이 가장 긴 증가 부분 수열 문제를 변형한 문제이다. 이전 문제와 다른 것은 dp[탐색위치]에 수열의 길이가 아니라 증가수열의 누적합을 저장하는 것이다. 우선 arr 배열에 입력값을 저장한다. dp[1]은 초기 누적합이므로 arr[1] 그대로를 저장한다. dp[i] 값을 저장하기 위해 i=2부터 n일 때까지 반복문을 돈다. 우선 현재 위치의 누적합 dp[i]에 값 그대로 arr[i]를 저장한다. 현재위치는 i이고, arr배열을 j=1부터 현재위치 이전(i-1)까지 탐색한다고 할 때, ​ 가장 큰 증가수열이여야 하므로 현재 값 arr[i]가 탐색값 arr[j]보다 크다면 이전누적합 + 현재위치값 과 현재누적합 중 큰 것을 dp[i]에 저장한다. (그래야 가장 큰 합의 증가수열 누적합을 저장할 ..

[PS] 백준 11053번 가장 긴 증가하는 부분 수열 - DP

문제 예제 풀이 이 풀이를 참고하였다. 이해하기 쉽게 그림까지 있고 잘 정리된 포스팅이어서 겨우 이해했다 ^^.. ​ 먼저 arr 배열에 입력 값을 넣는다. 반복문으로 dp[2]부터 dp[n]까지 1씩 위치를 이동(i = 2~n)해가며 dp배열에 가장 긴 수열의 길이를 저장할 것이다. dp[1]은 초기 시작지점이므로 1로 초기화한다. 또한 출력할 최대값을 저장할 변수를 1로 초기화 해두고 시작한다. 맨처음값 부터 검증위치(i) 이전까지 arr 배열을 탐색(j)할 것이므로 이중 반복문을 돌린다. i는 증가수열이 될 수 있는지 검증할 위치의 값이고, j는 1부터 i의 이전위치까지 탐색하기 위한 값이다. ​ 우선 dp[검증위치]값에 1을 저장해둔다. 탐색값보다 검증값이 크고 검증dp값(누적될 것임)이 현재dp..

[PS] 백준 2156번 포도주 시식 - DP

문제 예제 풀이 풀다가 영 감이 안와서 이전 문제에서 참고했던 블로그가 이해하기 쉽게 코드를 짜여있길래 또 참고한 풀이 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { Scanner in = new Scanner(System.in); int n = in..

[PS] 백준 9456번 스티커 - DP

문제 예제 풀이 이 풀이를 참고하였다. 스티커의 점수를 저장할 배열 arr[n+1][2]을 선언하고, 점수 합산결과를 저장할 dp[n+1][2] 배열을 선언한다. 첫번째 칸의 점수는 arr배열에서 dp배열로 dp[1][0], dp[1][1] 미리 저장해두고, 두번째 칸 부터 n번째 칸까지 i로 반복문을 돈다. i번째 칸의 점수를 마지막 값이라고 가정하면 최대값이 되기 위해서는 다음 그림과 같이 왼쪽 대각선 칸과 그 옆칸 중 합산값이 큰 값을 골라야 한다. 따라서 dp[i][0]이 마지막 값일 때에는 자신의 값 + dp[i-1][1]과 dp[i-2][1] 중 큰 값이 최대값이 된다. dp[i][1]이 마지막 값일 때는 자신의 값 + dp[i-1][0]과 dp[i-2][0] 중 큰 값이 최대값이 된다. d[..