DP

[백준] 2096 - 내려가기 (자바 Java)

[Gold V] 내려가기 - 2096 문제 링크 성능 요약 메모리: 236080 KB, 시간: 1228 ms 분류 다이나믹 프로그래밍(dp), 슬라이딩 윈도우(sliding_window) 문제 설명 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 ..

[백준] 2293 - 동전 1, 2294 - 동전 2 (자바 Java)

[Gold V] 동전 1 - 2293 문제 링크 성능 요약 메모리: 13068 KB, 시간: 128 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이 dp는 왜 해도..

[백준] 2225 - 합분해 (자바 Java) : DP

[Gold V] 합분해 - 2225 문제 링크 성능 요약 메모리: 13280 KB, 시간: 136 ms 분류 다이나믹 프로그래밍(dp), 수학(math) 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. dp는 항상 막막한데 점화식만 찾으면 쉽게 풀리는 것 같다 규칙이 있을까 해서 작은 경우의 수부터 하나하나 써봤는데 규칙을 찾을 수 있었다. dp[N][K..

[알고리즘] 최장 공통 부분 수열 (Longest Common Subsequence LCS)

목차 LCS (Longest Common Subsequence) 최장 공통 부분 수열 LCS의 길이 찾기 $$ x_m = y_n 이면 LCS(X_m, Y_n) = LCS(X_{m-1}, Y_{n-1})+1 $$ $$ x_m \neq y_n 이면 LCS(X_m, Y_n) = max(LCS(X_{m-1}, Y_{n}), LCS(X_{m}, Y_{n-1})) $$ https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence 문제 예시 9251번: LCS C[i-1][j] = A의 i-1번째, B의 j번째까지의 LCS Xi와 Yj가 같지 않다면 새로운 값을 추가할 수 없으니, 이전의 LC..

[백준] 2565 - 전깃줄 (자바/Java)

문제 링크 성능 요약 메모리: 13084 KB, 시간: 124 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에..

[백준] 11053 - 가장 긴 증가하는 부분 수열 (자바/Java)

문제 링크 성능 요약 메모리: 16964 KB, 시간: 192 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 가장 긴 증가하는 부분 수열 (LIS)를 구하는 문제다. 여러 가지 방법이 있지만 입력이 10..

[백준] 1463 - 1로 만들기 (자바/Java) : DP

문제 링크 성능 요약 메모리: 55224 KB, 시간: 224 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 정수 X가 2와 3 모두 나누어 떨어지지 않는 경우에는 X-1을 하면 된다. 문제는 2 또는 3과 나누어 떨어지는 경우에, 2나 3으로 나누는 것이 최적의 답이 아닐 ..

[백준] 2579 - 계단 오르기 (자바/Java) : DP

문제 링크 성능 요약 메모리: 13208 KB, 시간: 128 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다...

[백준] 12865 - 평범한 배낭 (자바/Java) : Knapsack Problem

[Gold V] 평범한 배낭 - 12865 문제 링크 성능 요약 메모리: 52664 KB, 시간: 192 ms 분류 다이나믹 프로그래밍(dp), 배낭 문제(knapsack) 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 ..

[백준] 17069 - 파이프 옮기기 2 (자바/Java)

문제 링크 성능 요약 메모리: 11880 KB, 시간: 84 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프..