Solve Algorithms/DP, BruteForce
-
11055 : 가장 큰 증가 부분 수열Solve Algorithms/DP, BruteForce 2020. 4. 28. 16:56
출처 : https://www.acmicpc.net/problem/11055 문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다. 접근 dp에 초기값으로 list와 같은 값을 넣어준다. dp..
-
1699 : 제곱수의 합Solve Algorithms/DP, BruteForce 2020. 4. 28. 16:53
출처 : https://www.acmicpc.net/problem/1699 문제 입력 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 출력 주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다. 접근 코드 package beak; 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)); BufferedWriter bw=new BufferedWriter(new OutputStream..
-
11053 : 가장 긴 증가하는 부분 수열Solve Algorithms/DP, BruteForce 2020. 4. 24. 13:08
출처 : https://www.acmicpc.net/problem/11053 문제 수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 접근 문제에서, '가장 긴'과, '증가하는', 이 두 부분에 초점을 맞춰야 한다. 증가하기만 해서는 안되고, 길이 역시 체..
-
10844 : 쉬운 계단 수Solve Algorithms/DP, BruteForce 2020. 4. 22. 13:42
출처 : https://www.acmicpc.net/problem/10844 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 접근 '쉬운' 계단 수이지만, 문제는 전혀 쉽지 않았다. 이번 문제는 구글링을 통해, 다른 블로그에서 풀이법을 알 수 있었다. 하지만, 잘 이해는 되지 않았다. 내가..