다이나믹 프로그래밍10

• 

  [Java] 백준 2293 : 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동전별로 k값을 만드는 경우의 수를 구해본다. 예제 입력에서의 동전 종류는 1,2,5이다. 1,2,5의 종류로 1~K까지의 수를 만들 수 있는 경우의 수를 구한다. 동전을 가지고 만들 수 있는 경우의 수를 찾아서 표를 채워주었다. - 동전 1을 가지고 1~10까지의 수를 만들 수 있는 경우의 수 - 동전 1과 2를 가지고 1~10까지의 수를 만들 수 있는 경우의 수 - 동전 1과 2,5 를 가지고 .. 코딩테스트/백준 2023. 3. 7.

• 

  [JAVA] 백준 9251 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문자열이 두 개가 입력이 되었을 때, 각 문자열의 부분수열에 해당하면서 가장 긴 수열을 찾는 문제이다. ACAYKP CAPCAK 이렇게 두개의 문자열이 입력이 되었다면 두 문자열의 LCS는 ACAYKP , CAPCAK 해서 ACAK이다. str1을 ACAYKP라고 하고, str1을 기준으로 str2를 비교하여 최대 길이를 알아내야 한다. 1. str1=.. 코딩테스트/백준 2023. 2. 27.

• [Java] 백준 12865 : 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net N=4 k=7이고, 물건 1 = 6 13 물건 2 = 4 8 물건 3 = 3 6 물건 4 = 5 12 일 때, 담을 수 있는 무게가 0일 때부터 7일 때까지 최대 가치를 찾으면 된다. 물건 1번을 담게 되면 무게 6 가치 13 이기 때문에 0~5까지는 담을 수 없기 때문에 0, 6과 7에서는 1번 외에는 더 담을 수 없기 때문에 1.. 코딩테스트/백준 2023. 2. 22.

• [Java] 백준 1309 : 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp [N+1][3]에서 dp [n][0] 은 사자가 n행에 한 마리도 없을 때, dp [n][1] 은 사자가 1행에서 왼쪽에 한 마리 있을 때, dp [n][2] 은 사자가 1행에서 오른쪽에 한 마리 있을 때를 의미한다. i=0일 때, dp [i][0] 일 때는 i-1행에서 사자가 어느 곳에 있어도 되므로, 앞행에 사자가 없거나 왼쪽에 있거나 오른쪽에 있는 경우를 더한다. => dp [i][0]=dp [i-1][0]+dp [i-1][1]+dp [i-1][2]; dp [i][1] 일 때는 i-1행에서 사자가 없거나 오른쪽에만 있어.. 코딩테스트/백준 2023. 2. 21.

• 

  [Java] 백준 11660 : 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 왼쪽 아래의 표를 중간과정을 반복해 구한 누적합이 오른쪽표의 값이다. 입력 예시의 2 2 3 4의 답은 27이다. 밑에 사진은 답을 구하기 위한 과정이다. 결과인 빨간 부분의 누적합은 (파란 부분의 누적합 -) (초록 부분 2개 각 누적합) + (초록색 겹친 부분)이다. import java.io.*; public class Main { static in.. 코딩테스트/백준 2023. 2. 17.

• [Java] 백준 11057 : 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 1 2 10 9 8 7 6 5 4 3 2 1 3 55 표에서 세로는 자릿수(N)를 의미한다. 가로는 우리가 이용할 수 있는 숫자(i)이다. 채워진 값은 i를 가지고 N자리수를 만들었을 때의 개수이다. 예를 들면 N=1 이면, 0,1,2,3,4,5,6,7,8,9를 만들 수 있다. N=2 이면,.. 코딩테스트/백준 2023. 2. 10.

• [Java] 백준 9465 : 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net card []에 가격을 넣어준다. 0번째 카드가 0 인 것은 나중에 최댓값 찾을 때를 위해 비워 둔 것이다. 0 50 10 100 20 40 0 30 50 70 10 60 이때 dp[][]에 각 해당하는 자리의 스티커를 떼어냈을 때의 최댓값을 더해 대입하면 된다. 해당 자리의 윗칸 스티커를 떼려면 직전에 아래칸 스티커를 떼었거나, 직전 아래칸 스티커는 떼지 않고 전전 아래칸 스티커를 떼.. 코딩테스트/백준 2023. 2. 9.

• [Java] 백준 11052 : 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net - 카드 i개가 들어 있는 카드팩 각 가격 price[] - 카드 N개를 구매하기 위한 최대금액 dp[] 아래처럼 진행이 되는데 여기서 규칙을 찾으면 된다. dp[0]=0, 1) 카드 한 장을 살 때 필요한 금액 dp[1]=price[1] =dp[0] + price[1] 2) 카드 두장을 살 때 필요한 금액 dp[2]=price[2] =dp[0] + price[2] dp[2]=price[1]*2 = dp.. 코딩테스트/백준 2023. 2. 8.

• 

  [Java] 백준 1149 : RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 모든 집을 칠하는 최솟값을 구해야 한다. 규칙은 아래와 같다. 현재 칠할 집의 색은 앞에 칠해진 집의 색과 다르면 된다. 1. RGB 값을 각각 저장한 다음 dp[][]에 이전에 칠해진 색상을 제외한 비용 중 최솟값을 구한다. 2. dp[]에 누적 비용을 저장한다. dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+R; dp[i][1]=Math.min(.. 코딩테스트/백준 2023. 2. 1.

• 백준 11726 : 2*N 타일링 _자바 Java https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net import java.io.*; import java.util.*; 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()); in.. 코딩테스트/백준 2023. 1. 11.