본문 바로가기

DP30

[백준/C++] 골드바흐흑흙의 추측 (No. 32647) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] A, B사이의 소수들의 합으로 K라는 수를 만들 수 있는지 라는 문제를 보고 처음에 단순히 경우의 수를 계산하면 안되겠다는 생각이 들었다. B-A 하지만, 모든 경우를 직접 계산하지 않고 소수의 합을 Memoization으로 몇 번 나왔는지 계산하면 중복되는 경우가 생기므로 빠르게 계산할 수 있겠다는 생각이 들었다. 예를 들어 2, 3, 5, 7의 소수가 있을 때를 아래 그림을 통해 생각해보자. 이렇게 덧셈을 해가며 계산하면 중복되는 경우가 생긴다.5의 경우 소수 5만 사용하는 경우와 2, 3을 더해 5를 만드는 .. 2024. 11. 13.

[백준/C++] 조 짜기 (No. 2229) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 문제에 대한 설명이 애매해서 추가하면, 나이로 정렬을 했기 때문에 붙어있는 사람들끼리 조를 이루어야한다는 조건이 추가되어야 한다. 즉, A, B, C 순서로 있다면, [A, C]로 조를 만들 수 없지만, [A, B, C]로 조를 만들 수 있다는 뜻이다. 이제 이를 이용해 문제를 풀어 나가면 된다. 만약 i번째 사람까지 조가 정해졌다면, 그때의 최대 값을 이용해 j번째 사람까지 조가 이루어졌을 경우의 최대값을 갱신해 나가면서 풀 수 있다. 이렇게 단계로 풀 수 있기 때문에 DP 배열을 이용해 풀 수 있다. dp[.. 2024. 10. 29.

[백준/C++] 마법천자문 (No. 23325) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 경우에 대해 계산을 하게되면 매우 많은 경우가 발생하므로 다른 방법으로 풀어야 한다. 이때, 잘 생각해보면 우리가 원하는 값은 최대 값이므로 특정부분까지 계산하는 방법이 매우 다양해도 최대값만 고려하고 다른 방법은 고려하지 않아도 된다는 것을 알 수 있다. 그러므로 이를 이용해 DP로 해결했다. 푸는 방법은 간단하다. DP[i] = i번까지 계산한 방법 중 최대값 으로 정의한다. 그러면 DP[i] 뒤에 이어지는 연산을 생각해보면 i+1은 무조건 연산자가 된다. 그리고 i+2는 무조건 숫자기 때문에 아래.. 2024. 10. 18.

[백준/C++] 벼락치기 (No. 14728) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 기준만 잘 잡으면 풀 수 있다. 공부할 수 있는 최대 시간이 10000이므로 아래와 같은 배열을 하나 만든다. 이 배열은 T시간동안 공부했을 경우 얻을 수 있는 점수의 최대값을 저장하는 배열이다.그리고 전부 -1로 초기화를 한 다음 시간이 0 인 경우만 0으로 초기화한다.여기서 DP[T] = -1일 경우는 현재 T시간을 공부하는 방법이 없다는 뜻이다. 그 후 입력을 받아 n개의 공부의 값을 이용해 위 배열을 채워나가면 된다.(이때, 과목에 대한 시간 = E, 성과 = V라고 하자) 10,000 부터 0 .. 2024. 10. 9.

[백준/C++] 합성함수와 쿼리 (No.17435) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 빠르게 해결하기 위해 Cycle이 생기는 순간을 기록해야하나? 의문이 들었다.그런데 아무리 생각해도 Cycle을 판단하는데 시간이 오래 걸릴 것으로 보여 다른 방법을 고민했다. 중간에 다른 사람의 힌트를 보니 DP를 이용해 문제를 푼 것을 보고 해결을 할 수 있었다. 함수를 2^k번 적용한 값을 저장하는 DP를 만들면, DP배열을 이용해 빠르게 계산을 할 수 있다. 함수를 2^k번 적용한 DP배열을 만드는 방법도 간단하다. x라는 수를 2^k번 적용해 x1이라는 수가 나오면, x1을 다시 2.. 2024. 9. 4.

[백준/C++] 색상환 (No. 2482) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 저번에 풀었던 RGB거리 2와 사실 크게 다르지 않은 문제다"> HTML 삽입미리보기할 수 없는 소스 단지 차이점이 있다면, 저번 문제에서는 가중치를 구해야 했다면, 이번 문제는 경우의 수를 구하는 것이다. 문제의 핵심은 색을 칠하기 위해서 i번째 색을 선택하면 i-1번째 색과 i+1번째 색을 선택할 수 없다는 것이다. 그러므로 i-1번째 색을 사용했다면, i번째 색을 사용할 수 없고 i-1번째 색을 사용하지 않았다면 i번째 색을 사용할 수 ㅣㅆ다는 점을 이용해 N번째 색에 도달할 동안 몇 개의 색을 선택했는.. 2024. 7. 3.

[백준/C++] RGB거리 2 (No. 17404) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N번째 집이 N-1번째 집과 N+1번째 집의 색과 다르게 색칠하는 경우 최소의 비용을 구하는 문제다. 단, 1번 집과 N번째 집도 서로 색이 달라야 한다. 즉, 처음과 끝이 연결된 원탁과 같은 경우다. 하지만 처음과 끝이 연결됐다고 해서 크게 어려운 문제는 아니다.처음과 끝의 경우를 고려해 탐색하면 쉽게 풀 수 있는 문제다. i번째 집을 색칠하기 위해서는 마지막에 색칠된 i-1번째 집과 i번째 집의 색이 다르면 된다.그러므로 i번째 집을 R로 색칠하기 위해서는 i-1번째 집을 G, B로 색칠하는 경우만 고려하.. 2024. 7. 1.

[백준/C++] 트리의 독립집합 (No. 2213) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 아무 생각 없이 하나의 노드를 기준으로 두번 검사하면 되겠다는 생각을 했다. 하지만 예제의 입력을 보자마자 착각했다는 것을 깨닫고 다시 풀었다... 새로 푼 방법은 두가지 경우로 나눠서 계산하는 방법으로 트리를 그리면서 계산하는 방법이다. 먼저 그래프가 트리의 형태이므로 한 정점을 기준으로 트리를 그린다. 이후 현재 노드와 하위 노드들(자식 노드들)의 값을 포함해 만들 수 있는 독립집합의 최대값을 DP라는 배열에 저장한다. DP라는 배열을 그리는 이유는 중복된 계산을 줄이기 위해서다. 어떤 .. 2024. 6. 9.

[백준/C++] ACM Craft (No. 1005) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 건물을 짓기 위해서 다른 건물을 먼저 지어야 된다는 선행조건이 있는 문제다. 이때, 각 건물은 동시에 지을 수 있다. 그러므로 특정 건물을 짓기 위해 필요한 시간을 아래와 같이 표현할 수 있다.Build(X) = max( Build (X건물을 짓기 위해 사전에 지어야 하는 건물) ) + (X 건물만 짓는데 걸리는 시간)그러므로 이 문제는 DP 문제로 생각할 수 있다. X건물을 짓기 위한 다른 건물을 짓는 시간을 알면, X건물을 짓는데 걸리는 시간을 알 수 있기 때문이다.(즉, 작은 문제를 해결함으로써 큰.. 2024. 6. 4.

[백준/C++] 트리와 쿼리 (No. 15681) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 루트노드가 주어지면 그 노드를 기준으로 트리를 그리면 되는 문제다. 단지 그냥 트리를 그리는 것과 다른 점이 있다면, 자식 노드의 수가 몇 개 인지 쿼리를 통해 출력한다는 점이다. 여기서 매번 쿼리가 들어올 때 마다 자식 노드의 수를 계산한다면 매우 많은 반복이 생기게 된다. 그러므로 애초에 트리를 그릴 때 자식노드가 몇 개 인지 return을 해준다면 한번의 트리를 그림으로써 모든 노드의 자식의 수를 알 수 있게 된다. 이제 아래 그림을 통해 어떻게 진행되는지 알아보자 위 그림과 같은 트리가 있을 경우 트리.. 2024. 6. 3.

[백준/C++] 경찰차 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 이전에 풀었던 숫자 타자 대회와 비슷하다는 느낌을 받았다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 다른 점은 w가 1000으로 컸기 때문에 문제의 시간복잡도가 O(n^2)인지 아닌지 고민을 많이했다.고민해본 결과 다행히 시간복잡도 O(n^2)으로 풀 수 있다는 생각이 들었고, 아이디어를 구현했다. 아이디어는 다음과 같다.2차원 배열 DP[A][B]를 만들고 1번째 경찰차가 A 위치에 있으며, 2번째 경찰차가 B 위치에 있는 경우에 이동거리의 최소값으로 정의한.. 2024. 5. 9.

[백준/C++] LCS 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 LCS 문제로 Memoization을 잘 이용해 문제를 풀 수 있다. 풀이를 고민하다가 두 문자를 비교해 같은 경우 이전에 구했던 LCS를 이용해 경우를 추가하면 되겠다는 생각이 들었다. 그래서 이전의 결과를 이용하기 위해 2차원 배열을 만들고 다음과 같이 정의했다. (DP[i][j] = 1번 문자열의 1~i번 문자와 2번 문자열의 1~j번 문자를 이용해 LCS를 만든 경우의 최대길이) 이제 정의를 이용해 아래 예시를 따라가 보자. 그림에서 빨간 네모가 색칠해진 칸을 DP[i][j]라고 하자.그러면 이 경우.. 2024. 5. 8.

[백준/C++] 앱 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀 때, 냅색 문제와 같이 풀었다. M의 크기를 갖는 배열을 만든 다음 i 만큼의 메모리를 cost를 주고 만들 수 있다면 새롭게 비용을 주고 특정 메모리를 만들 수 있는지 체크했다. 이렇게 풀면 통과는 되지만 10,000,000 * 100의 연산을 해야하기 때문에 비효율적 이었다. 다른 풀이가 있을까 찾던 중 메모리가 기준이 아니라 cost를 기준으로 하는 풀이가 있었다. DP[N][cost]을 만들고 여기에 메모리를 저장 하는 방법이다. 아래 그림을 따라 진행해보자 먼저 처음에 위 그림과 같이 초기화를 한다. 이후 첫번째 비용과 메모리를 이용해 Cost를 써서 얼마의 메모리를 만들 수 있는지.. 2024. 4. 7.

[백준/C++] 동전 1 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 k의 크기가 10000으로 제한되어 있기 때문에 쉽게 풀 수 있는 문제다. 동전의 가치가 전부 다르고 몇 개를 사용해도 되며, k원을 만드는 모든 경우의 수를 구해야 된다. for문으로 j원의 돈을 만들 수 있으면 j원에 coin을 더해 [j+coin]원을 만들 수 있다. 이때, coin을 여러개 사용할 수 있으므로 [j+coin*2], [j+coin*3] ... 도 만들 수 있다. coin에 숫자를 곱해 더하는 방법도 있겠지만, 좀 더 편한 방법이 있다. 예를 들어 2, 4의 동전이 주어지고 k가 10이라고 하자 그러면 2로 만들 수 있는 돈의 가치에 대한 경우의 수는 아래 그림과 같다. 그러면 2로.. 2024. 4. 6.

[백준/C++] 양팔저울 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 정말 풀 수 있나? 의문이 들었다.왜냐하면 아무리 DP로 푼다고 해도, 시간 복잡도는 O(3^n)이 되기 때문이다. (n은 추의 개수) 여기서 3^n인 이유는 아래와 같이 3가지 경우가 존재하기 때문이다. 1. 구슬 쪽에 추를 올리는 경우2. 추를 사용하지 않는 경우3. 구슬 반대편에 추를 올리는 경우 그렇기 때문에 시간 복잡도는 O(3^n)이다. 한번 최악의 경우를 상상해 보면 추의 무게가 1, 3, 9 ,27 ... 처럼 3의 배수로 늘어나는 경우이다. (중복해서 만들어지는 추의 무게가.. 2024. 4. 5.

이전 1 2 다음

티스토리툴바