전체 글

[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[..

[PS] 백준 2193번 이친수 - DP

문제 예제 풀이 이 문제도 앞서 쭉 푼 문제들과 비슷하다. 오히려 조건이 더 단순해서 쉽게 풀었다. 이친수의 조건은 다음과 같다. 0과 1만 사용 (이진수) 1이 연속되면 안된다. 0으로 시작하지 않는다. dp[자리길이][마지막자릿값] 배열을 선언한다. 마지막 자릿값이 0이면 뒤에 0이나 1이 올 수 있다.(두 가지 경우의 수) 마지막 자릿값이 1이면 뒤에 0만 올 수 있다.(한 가지 경우의 수) ​ 4자리와 5자리 이친수의 예를 들어보자 dp[4][0] = {1000, 1010} dp[4][1] = {1001} dp[5][0] = {10000, 10100, 10011} dp[5][1] = {10001, 10101} 따라서 dp[n][0] = dp[n-1][0] + dp[n-1][1] 이고 dp[n][1..

[PS] 백준 11057번 오르막 수 - DP

문제 예제 풀이 이 문제는 쉬운 계단 수 문제의 연장선이다. 주의할 점은 계단 수와 달리 숫자를 0부터 시작할 수 있다. 똑같이 dp[자릿수길이][마지막자릿수] 이차원배열을 사용하였고, 다음 필기와 같은 규칙성을 찾을 수 있다. 따라서 도출되는 점화식 dp[n][i] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + ... + dp[n-1][i]를 사용하여 푼다. 코드 import java.util.Arrays; import java.util.Scanner; public class Main { final static long mod = 10007; public static void main(String[] args) { Scanner sc = new Scanner(System.in..