본문 바로가기

DP33

[백준/C++] 꺾이지 않는 마음 1 (No. 26142) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제를 처음 봤을 때 활을 쏠 용이 정해지면 그 용을 다시 쏠 필요는 없겠다는 생각이 들었다. 왜냐하면 하루에 하나의 활만 쏠 수 있기 때문에 a일에 용을 쏘고 a+b일에 용을 다시 쏜다면 애초에 a+b일에 용을 쏘면 되기 때문이다. 이를 바탕으로 활을 맞출 용이 정해진다면 그 용들 중 성장하는 키의 수치가 가장 큰 용을 나중에 맞추면 최대값을 얻는다는 것을 알 수 있다. 문제는 활을 맞출 용을 정하는 방법이다.D[i]와 H[i]값이 있기 때문에 단순히 그리디하게 K일에 어떤 용들을 맞출지 정하기가 어렵다. 다행히 N의 값이 10000으로 작기 때문에 DP를 활용한다면 i번째 용을 포함할지 말지를 .. 2025. 2. 2.

[CodeForce/C++] F. Multiplicative Arrays (Div.3) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 페르마의 소정리와 DP를 이용해서 풀 수 있는 문제다. 잘 생각해보면 이 문제는 k를 소인수 분해하는 것으로 시작할 수 있다는 것을 알 수 있다.왜냐하면 최대 길이 n의 배열의 곱이 k가 나오기 위해서는 배열 a의 안에 k의 약수들이 있다는 뜻이 되기 때문이다. 이를 이용하면 배열의 길이가 n일 때, 1을 제외한 k의 약수의 개수를 m이라고 하면 n-m개의 1과 m개의 k의 약수로 이루어진 배열의 조합을 구하는 문제로 볼 수 있다. 이를 이용해 DP로 문제를 해결할 수 있다. 아래와 같이 DP를 정의 하자. DP[k][i] = 1이 아닌 i개의 수를 곱해서 k를 만드는 경우의 수 그러면 .. 2025. 1. 23.

[백준/C++] 유아와 곰두리차(No. 20951, 새해 기념) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 잘 생각해보면 이미 이용한 경로를 통해서도 다시 방문을 할 수 있으므로, i번째에 N번째 노드를 방문한 경우를 이용해 i+1번째에 각 노드에 방문할 수 있는 경로가 몇 개인지 계산하면 되는 문제다. 이를 잘 생각해보면 이전에 작은 문제의 해결방법을 이용해 다음 문제를 풀 수 있으므로 DP 문제로 생각할 수 있다. 그림으로 보면 초록색 부분을 채워 나가면 된다. N개의 노드가 존재하고 i번째에서 N번째 노드를 방문한 경우를 이용해 i+1번째 노드에는 몇 가지 경로가 존재하는지 빠르게 계산할 수 있다. [아이디어 정리]N * 8 크기의 배열을 만든다.현재 i번째 이동했을 때, N번째 노드를.. 2025. 1. 1.

[백준/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.

이전 1 2 3 다음

티스토리툴바