본문 바로가기

DP14

[Java] BOJ 9084번 동전 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 문제에서 주어진 수는 너무 큰 관계로 3개의 동전 2원, 3원, 5원으로 10원을 만드는 경우를 구해보겠습니다. 1 2 3 4 5 6 7 8 9 10 2원 0 1 0 1 0 1 0 1 0 1 2원의 경우 위와 같은데 이때, 총경우의 수를 구해야 하므로 구한 결괏값을 그대로 유지하고 새로 갱신을 해나가야 합니다. 다음으로 3원의 경우를 보겠습니다. 예를 들어, 3원의 경우 앞서 2원으로 만들 수 있는 경우의 수들.. 2021. 7. 16.
[Java] BOJ 11054번 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 가장 긴 바이토닉 부분 수열은 앞에서부터 가장 긴 증가하는 부분 수열의 개수 + 뒤에서부터 가장 긴 증가하는 부분 수열의 개수에다가 자기 자신은 두 번 들어갔으므로 1을 빼어 해결할 수 있었습니다. 예를 들어, 수열 1 5 2 1 4 3 4 5 2 1의 경우를 보면, 빨간색으로 쓴 1번은 앞에서부터 증가하는 부분 수열의 개수이고, 파란색으로 쓴 2번의 경우 뒤에서 부터 가장 긴 증가하는 부분 수열이 됩니다. 그리고 LBS는 초록색처럼 1번과 2번을 더해주되 i번째의 숫자가 두 .. 2021. 5. 5.
[Java] BOJ 1699번 제곱수의 합 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 최대 항의 최대 개수는 1^2으로만 이루어진 경우이므로 memo[i] = i로 초기화하였습니다. i - (j ^ 2)인 수의 최대항의 개수 + 1중 최소인 값을 찾아 해결했습니다. 예를 들어 i = 5, j = 2라면 5 - (2 ^ 2) = 1이므로 memo[1]의 최대 항의 최소 개수는 1입니다. 때문에, 1 + (2 ^ 2)를 하면 원래 i인 5가 되므로 문제에서 요구한 제곱수의 합으로 표현되므로 memo[1] .. 2021. 4. 30.
[Java] BOJ 9251번 LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 DP를 이용해서 해결했습니다. 코드 주석에 설명을 포함했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static String S1, S2; public static int[][] memo; public static void main.. 2021. 4. 29.
[Java] BOJ 1904번 01타일 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 점화식인 memo[i] = memo[i - 1] + memo[i - 2]를 사용해서 해결했습니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public final static int mod = 15746; public static int N; public static int[] memo = new .. 2021. 4. 28.
[Java] BOJ 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 10 2 자리 10 9 8 7 6 5 4 3 2 1 55 3 자리 55 45 36 28 21 15 10 6 3 1 220 DP를 사용하여 위의 표처럼 계산을 진행하여 해결했습니다. 2자리일 때의 2로 시작하는 오르막 수는 2보다 크거나 같은 수들로 이뤄질 수 있으므로 2자리 바로 이전의 미리 구해둔 1자리일 때의 2 이상의 오르막 수 개수를.. 2021. 4. 22.

티스토리툴바