dp
-
[Baekjoon Online Judge] 11727번: 2xn 타일링 2문제 풀이/Baekjoon Online Judge 2021. 2. 10. 15:58
11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 요구사항 - 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성한다. 입력 - 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 - 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 2021/01/30 - [문제 풀이/다이나믹 프로그래밍] - [Baekjoon Online Judge] 11726번: 2xn 타일링 [Baekjoon Online Judge] 11726번: 2xn 타일링 11726번: ..
-
[Baekjoon Online Judge] 10844번: 쉬운 계단 수문제 풀이/Baekjoon Online Judge 2021. 2. 6. 17:39
10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 요구사항 - 인접한 모든 자리수의 차이가 1인 수를 계단 수라고 한다. - 수의 길이 n이 주어지면 계단 수가 몇 개 인지 구한다. - 수는 0으로 시작할 수 없다. 입력 - 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 - 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 자리 수가 1일 때 계단 수는 1, 2, 3, 4, 5, 6, 7, 8 9로 9개 이다. 자리 수가 2일 때 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98..
-
[Baekjoon Online Judge] 10870번: 피보나치 수 5문제 풀이/Baekjoon Online Judge 2021. 2. 6. 16:21
10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 요구사항 - 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. - 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. 입력 - 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다. 출력 - 첫째 줄에 n번째 피보나치 수를 출력한다. import java.io.BufferedR..
-
[Baekjoon Online Judge] 1912번: 연속합문제 풀이/Baekjoon Online Judge 2021. 2. 6. 16:10
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 요구사항 - n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 입력 - 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 - 첫째 줄에 답을 출력한다. n개의 정수로 이루어진 임의의 수열 중 연속 된..
-
[Baekjoon Online Judge] 11053번: 가장 긴 증가하는 부분 수열문제 풀이/Baekjoon Online Judge 2021. 2. 6. 14:57
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 요구사항 - 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구한다. 입력 - 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. - 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 - 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 수열의 각 항목을 비교하며, 해당 자리 까지 가장 긴 증가하는 부..
-
[Baekjoon Online Judge] 2748번: 피보나치 수 2문제 풀이/Baekjoon Online Judge 2021. 2. 1. 21:23
2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 요구사항 - 피보나치 수는 0과 1로 시작한다. 0 번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이다. 입력 - 첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다. 출력 - 첫째 줄에 n번째 피보나치 수를 출력한다. import java.io.BufferedReader; import java.io.BufferedWriter; import java...
-
[Baekjoon Online Judge] 1932번: 정수 삼각형문제 풀이/Baekjoon Online Judge 2021. 2. 1. 11:21
1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 요구사항 - 맨 위층 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성한다. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 입력 - 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 - 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 상각형의 밑단에서 부터 dp 테이블을 채우고, 그중에 최대값..