백준/DP 다이나믹 프로그래밍
-
11048 이동하기백준/DP 다이나믹 프로그래밍 2022. 5. 17. 22:55
1. 풀이 문제 예시 1로 설명하겠다. 3 4 1 2 3 4 0 0 0 5 9 8 7 6 map 배열에 각 위치의 사탕 개수를 입력한다. 즉, 1 2 3 4 0 0 0 5 9 8 7 6 이 값들을 map 배열에 입력한다. 문제에서 한 점은 1) 오른쪽, 2) 아래쪽, 3) 오른쪽 아래로 이동 가능하다고 했다. 즉, (1,1) 위치에서 이동 가능한 곳은 아래 그림과 같다. 그렇기 때문에 위치(2,2)에 있는 준규가 가질 수 있는 사탕 개수의 최댓값은 (2,2) 위치의 사탕 개수 + (1,1), (1,2), (2,1) 위치 사탕 개수 중 제일 큰 값이다. 자세히 설명하자면, (1,1) 에서 오른쪽, 아래쪽, 오른쪽 아래 방향으로 이동 가능하다. 그런데 이것은 출발지 -> 도착지 방향이다. 그렇다면 도착지에서..
-
가장 긴 증가하는 부분 수열 11053백준/DP 다이나믹 프로그래밍 2022. 2. 8. 19:52
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int input [] =..
-
11057 오르막 수백준/DP 다이나믹 프로그래밍 2021. 10. 26. 20:32
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 동적 계획법을 잘 몰라서 아래 참고자료의 블로그를 참고했다. 문제에서 찾고자 하는 답을 다음과 같이 나타낼 수 있다. a: 자리수 b: 끝자리 즉, a=2이고, b=1 이면 자리수가 2자리 이고, 1로 끝나는 오르막 수를 찾으면 01 11 로 2개가 나온다. 그럼 표에 나온 값들의 개수를 나타낸 표는 다음과 같다. 즉 위 표에서 즉, a=2이고, b=1 일 때,..
-
9465 스티커백준/DP 다이나믹 프로그래밍 2021. 10. 23. 21:06
https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 예제 입력 1 두번째로 나온 값을 표현했다. 10에서 다음 번으로 이동할 때, 아래(20), 오른쪽(30)으로는 이동 못하고, 위 그림에서 나타낸 것처럼 40,30 만 고려하면 된다. 그 이유는 다음과 같다. 1. 10->10(위쪽 3번째 값) (이동) 10에서 10으로도 물론 이동가능할 것이다. 하지만, 10->10으로 바로 이동하는 것보다는, 10(윗쪽 첫번째) ->40(아래쪽 두번..
-
11052 카드 구매하기백준/DP 다이나믹 프로그래밍 2021. 10. 23. 16:12
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ..
-
11726 2xn 타일링백준/DP 다이나믹 프로그래밍 2021. 10. 21. 21:49
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 : dp[n] = dp[n-1]+dp[n-2] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static int dp []; public static void main(String[] args) throws IOException { Buffered..