DP10 [Problem Solving] BOJ 1495: 기타리스트 문제 출처: https://www.acmicpc.net/problem/1495 i번째 곡을 연주하기 전에 현재 볼륨 P에서 V[i]만큼 줄이거나 V[i]만큼 키워야할 때, 마지막 곡의 볼륨의 최댓값을 구하는 문제이다.볼륨은 최소 0, 최대 M어야하고, 중간에 범위를 벗어나면 안된다. 이 문제는 2차원 DP로 풀 수 있다.DP테이블을 다음과 같이 정의할 수 있다.DP[i][j]: i번째 곡을 연주할때 j라는 볼륨으로 설정될 수 있는지에 대한 여부 (true / false) 풀이 과정은 다음과 같다. 1.V[0] = S일 때, DP[0][V[0]] 를 true로 설정한다. 2.0 N - 1)0 M)인 i, j에 대하여 DP[i][j]가 true일 때,j + V[i + 1]가 M이하라면 -> DP[i + .. 2025. 5. 19. [Problem Solving] BOJ 2533: 사회망 서비스(SNS) 문제 출처: https://www.acmicpc.net/problem/2533 친구 관계 트리가 주어졌을 때, 모든 노드가 새로운 아이디어를 수용하기 위해 필요한 최소 얼리 어답터 수를 구하는 문제이다.얼리 어답터는 인접한 모든 노드에 새로운 아이디어를 알릴 수 있다. 이 문제는 DP + DFS 방식으로 해결 할 수 있다. 우선 DP 테이블을 정의해야한다. DP[i][0]: i번째 노드가 얼리 어답터가 아닌 경우, 이 노드가 루트 노드인 서브트리의 최소 얼리 어답터 수DP[i][1]: i번째 노드가 얼리 어답터인 경우, 이 노드가 루트 노드인 서브트리의 최소 얼리 어답터 수 부모 노드가 얼리 어답터가 아니라면 자식 노드는 반드시 얼리 어답터여야 한다.-> DP[parent][0] += DP[child][.. 2025. 5. 11. [Problem Solving] BOJ 1516 : 게임 개발 문제 링크 : https://www.acmicpc.net/problem/1516 각각의 건물(노드)이 지어지는 최소 시간을 구하는 문제이다. 각 건물은 먼저 지어져야 하는 건물이 지어진 후에 지어지기 시작할 수 있다. 1. 그래프를 입력받고, 위상정렬 알고리즘을 수행한다.2. dp테이블을 각 건물이 지어지는 시간으로 채운다.3. 위상정렬된 순서대로 현재 노드에서 인접한 노드의 dp값을 max(인접 노드의 현재 dp 값, 현재 노드의 현재 dp값 + 인접 노드가 지어지는 시간)으로 업데이트한다. #include #include #include #include #include #include #include #include #include #include #define endl '\n'using namesp.. 2025. 1. 2. [Problem Solving] BOJ 10942 : 팰린드롬? 문제 링크 : https://www.acmicpc.net/problem/10942#include #include #include #include #include #include #define endl '\n' using namespace std; int N, M; vector v; vector query; int dp[2001][2001]; void input() { cin >> N; v.resize(N + 1); for (int i = 1; i > v[i]; } cin >> M; for (int i = 0; i > S >> E; query.push_back({S, E}); } } void solution() { for (int i = 1; i 2024. 8. 5. [Problem Solving] BOJ 2096 : 내려가기 문제 링크 : https://www.acmicpc.net/problem/2096#include #include #include #include #include #define endl '\n'using namespace std;int N;int arr[2][3];int mindp[2][3];int maxdp[2][3];int maxVal;int minVal;void input(){ cin >> N; for (int j = 0; j > arr[0][j]; }}void solution(){ for (int i = 0; i > arr[1][j]; maxdp[1][0] = max(maxdp[0][0], maxdp[0][1]) + arr[1][0]; maxdp[1][1.. 2024. 7. 30. [Problem Solving] BOJ 2133 : 타일 채우기 문제 링크 : https://www.acmicpc.net/problem/2133#include #include #include #define endl '\n'using namespace std;long long N;long long dp[31] = {0};void input(){ cin >> N; dp[2] = 3;}void solve(){ for (long long i = 4; i = 2; j -= 2) { dp[i] += dp[j] * 2; } dp[i] += 2; }}void output(){ cout 3 * N 타일을 2 * 1 타일과 1 * 2 타일로 채울 수 있는 경우의 수를 출력하는 문제이다. 우선 손으로.. 2024. 7. 14. 이전 1 2 다음
