초코민트냠냠블로그

이 문제는 유명한 DP문제 중 하나로 0-1 knapsack problem입니다. 배낭에 무게 제한을 넘지 않으면서 내용물의 가치의 합이 최대가 되는 물건들의 부분집합을 구하는 문제입니다. 물건을 쪼갤 수는 없습니다. 모든 부분집합을 구하는 경우는 $O(2^n)$의 시간이 걸리기 때문에 시간초과가 나게 됩니다. 점화식 배낭 문제에서 dp의 점화식은 다음과 같습니다. dp배열에서 x축은 물건의 인덱스 번호, y축은 자연수인 무게 값이 들어가게 됩니다. 기본적인 아이디어는 i 번째 물건을 집어 넣는 경우와 넣지 않는 경우 중에서 큰 값을 dp테이블에 저장하는 것입니다. 예제를 살펴보겠습니다. 가방의 무게 제한은 7이고 물건의 무게와 가치가 다음과 같이 주어졌습니다. 6 13 4 8 3 6 5 12 첫 번째 ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제를 보면 4개의 이어지는 칸의 합이 최대인 값을 구하면 됩니다. 우리가 사용할 수 있는 모양을 보면 테트리스 조각이랑 똑같은데 T블록( ㅗ블록) 을 제외한 나머지 블록들은 간단히 DFS를 사용하면 모든 경우를 구할 수 있습니다. T블록의 경우는 따로 분리해서 코드를 작성해주면 됩니다. 각 칸의 숫자는 1000을 넘지 않는 자연수이므로 int 범위에서도 충분합니다. #include #includ..

https://www.acmicpc.net/problem/11718 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net 입력 받은 대로 출력하는 간단한 문제입니다. 각 줄은 알파벳 소문자, 대문자, 공백, 숫자로 이루어져 있습니다. 공백을 포함하고 있기 때문에 cin을 사용하지 않고 한 줄을 통째로 읽는 getline()함수를 씁니다. getline() 함수는 헤더에 있습니다. 아래는 제 코드입니다. #include #include using namespace std; int main() { wh..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A 31) 위의 조건으로 인해 연산을 하는 중간에는 수가 짝수이거나, 일의 자리 수가 1인 두 가지 조건을 반드시 만족합니다. 그러므로 B에서 2를 나누거나, 오른쪽 1을 삭제하는 두 가지 연산을 하는 방법으로..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 이번 문제는 트리의 간선을 입력으로 받고 2부터 마지막 노드까지의 부모 노드를 출력하는 문제입니다. 트리도 그래프의 일종이므로 저는 BFS를 써서 문제를 풀었습니다. 트리의 루트 노드는 1이므로 1을 시작으로 BFS를 돌리면서 노드를 방문할 때 이전 노드의 값을 답으로 저장하면 됩니다. DFS로도 가능합니다. 아래는 제 코드입니다. #include #include #include using namespace std; int n; vectoradj[100002]..