다이나믹 프로그래밍

문제출저 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.lang.reflect.Array; import java.nio.Buffer; import java.securi..

문제출저 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 소스코드 package studyGroup.June.june27; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 백준2096내려가기 { static int n; // 줄의 갯수 static String..

문제출저 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 소스코드 package studyGroup.June.june10; import java.util.*; import java.io.*; import java.lang.*; /* 어디서 시작되는지는 모른다. */ public class 백준2098외판원순회 { static int n; // 도시의 수 static int[][] board; static i..

문제출저 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 소스코드 package studyGroup.June.june9; import java.util.*; import java.io.*; public class 백준11054가장긴바이토닉부분수열 { static int n; static int[] board; public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

문제출저 : https://www.acmicpc.net/problem/14945 14945번: 불장난 랩실의 크기가 3일 경우 (기웅, 민수)가 이동 가능한 방법은 (아래-아래, 대각-아래), (아래-아래, 대각-대각), (아래-대각, 대각-대각), (대각-아래, 아래-아래), (대각-대각, 아래-아래), (대각-대각, www.acmicpc.net 소스코드 : package studyGroup.June.june3; import java.util.*; import java.io.*; /* 중복되는 문제가 있기 때문에 DP로 접근한다. 이동할 수 있는 경우의 수는 4가지이다. 1. 둘 다 아래 (거리 그대로) 2. 1번 아래, 2번 오른쪽 (거리 +1) 3. 1번 오른쪽, 2번 오른쪽 (거리 그대로) 4. ..