[백준 17216] 가장 큰 감소 부분 수열 (C++)
https://www.acmicpc.net/problem/17216문제수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열은 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 이고, 합은 186이다. 입력 첫째 줄에 수열 A의 크기 N(1 ≤ N ≤ 1000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다.(1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 합이 가장 큰 감소 부분 수열의 합을 출력한다. 문제 풀이LIS 알고리즘.일반적인 LIS 알고리즘에서는 dp 배열에 증가하는 형태이..
2024. 7. 16.
[백준 16967] 배열 복원하기 (C++)
https://www.acmicpc.net/problem/16967문제크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐진다.즉, 배열 B의 (i, j)에 들어있는 값은 아래 3개 중 하나이다.(i, j)가 두 배열 모두에 포함되지 않으면, Bi,j = 0이다.(i, j)가 두 배열 모두에 포함되면, Bi,j = Ai,j + Ai-X,j-Y이다.(i, j)가 두 배열 중 하나에 포함되면, Bi,j = Ai,j 또는 Ai-X,j-Y이다.배열 B와 정수 X, Y가 주어졌을 때, 배열 A를 구해보자. 입력첫째 줄에 네 정수 H, W, X..
2024. 7. 11.
[백준 7453] 합이 0인 네 정수 (C++)
https://www.acmicpc.net/problem/7453문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력합이 0이 되는 쌍의 개수를 출력한다. 문제 풀이MITM 알고리즘과 투포인터를 같이 사용하는 문제.A, B, C, D 4개 배열을 모든 A+B를 저장하는 벡터 v1, 모든 C+D를 저장하는 벡터 v2 2개로 만들어 시간 복잡도를 줄인다. 벡터를 사용해 ..
2024. 7. 10.
[백준 2295] 세 수의 합 (C++)
https://www.acmicpc.net/problem/2295문제N(5 ≤ N ≤ 1,000)개의 자연수들로 이루어진 집합 U가 있다. 이 중에서 적당히 세 수를 골랐을 때, 그 세 수의 합 d도 U안에 포함되는 경우가 있을 수 있다. 이러한 경우들 중에서, 가장 큰 d를 찾으라.예를 들어 {2, 3, 5, 10, 18}와 같은 집합이 있다고 하자. 2+3+5 = 10이 되고, 이 수는 집합에 포함된다. 하지만 3+5+10 = 18이 되고, 이 경우가 세 수의 합이 가장 커지는 경우이다. 입력첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에 차례로 U의 원소가 하나씩 주어진다. 주어진 U는 집합이 되므로 입력되는 두 수가 같아서는 안 된다. U의 원소는 200,000,000보다 작거나 같은 자연수이..
2024. 7. 9.
