본문 바로가기

728x90

SMALL

BAEKJOON/다이나믹 프로그래밍

(58)

백준 16287번 [Parcel](C++) -yes6686- 티스토리 백준 문제 풀이: 16287 [Parcel]문제 링크: https://www.acmicpc.net/problem/16287문제 설명:주어진 무게 w를 네 개의 서로 다른 원소의 합으로 만들 수 있는지를 확인하는 문제입니다.배열의 원소를 두 개씩 묶어서 합을 구한 후, 나머지 두 개가 해당 값과 일치하는지 확인하는 방식으로 풀 수 있습니다.문제 해결 코드#include #include #include using namespace std;int arr[5001]; // 원소 배열pair arrs[400001]; // 두 수의 합을 저장하는 배열int main() { ios::sync_with_stdio(false); cin.tie(NULL); int w, n; cin >> w >> n;..

백준 17485번 [진우의 달 여행 (Large)](C++) -yes6686- 티스토리 백준 문제 풀이: 17485 [진우의 달 여행 (Large)]문제 링크: https://www.acmicpc.net/problem/17484문제 설명:우주선이 지구에서 출발하여 달에 도착할 때까지 연료 소비량이 최소가 되도록 경로를 선택하는 문제입니다.이동 규칙은 다음과 같습니다:각 행에서는 좌하단(↙), 아래(↓), 우하단(↘)으로만 이동할 수 있습니다.연속해서 같은 방향으로 이동할 수 없습니다.목표는 (0, x) 위치에서 출발하여 (n-1, y)에 도착하는 최소 연료 소비량을 구하는 것입니다.문제 해결 코드#include #define INF 1e9using namespace std;int arr[1001][1001]; // 각 위치의 연료 소비량int dp[3][1001][1001]; // 각 방향..

백준 1520번 [내리막 길](C++) -yes6686- 티스토리 백준 문제 풀이: 1520 [내리막 길]문제 링크: https://www.acmicpc.net/problem/1520문제 설명:지도의 각 칸에는 높이가 주어지며, (0,0)에서 시작하여 (n-1,m-1)까지 가는 경로 중에서 항상 내리막길만 이동하는 경우의 수를 구하는 문제입니다.즉, 현재 위치보다 낮은 위치로만 이동할 수 있으며, 가능한 모든 경로의 개수를 출력해야 합니다.문제 해결 코드#include using namespace std;int dx[4] = { 1, -1, 0, 0 };int dy[4] = { 0, 0, 1, -1 };int arr[501][501]; // 지도 정보long long dp[501][501]; // 메모이제이션 배열int n, m;// 깊이 우선 탐색 (DFS) + 동적..

백준 10942번 [팰린드롬?](C++) -yes6686- 티스토리 백준 문제 풀이: 10942 [팰린드롬?]문제 링크: https://www.acmicpc.net/problem/10942문제 설명:1부터 n까지 번호가 매겨진 수열이 주어졌을 때, 특정 구간이 팰린드롬인지 확인하는 문제입니다. 팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열을 말합니다. 각 쿼리마다 구간이 팰린드롬인지 (1)인지 아닌지 (0)를 출력해야 합니다.문제 해결 코드#include using namespace std;int arr[2001];int r[2001][2001];// 팰린드롬 확인 함수int check(int a, int b) { if (r[a][b] != 0) return r[a][b]; if (a >= b) return 1; if (arr[a] == arr[b..

백준 9252번 [LCS 2](C++) -yes6686- 티스토리 백준 문제 풀이: 9252 [LCS 2]문제 링크: https://www.acmicpc.net/problem/9252문제 설명:두 문자열 A와 B가 주어졌을 때, 두 문자열의 최장 공통 부분 수열(LCS)을 구하는 문제입니다. LCS는 두 문자열에 공통으로 들어 있는 부분 수열 중 가장 긴 것을 의미합니다. 결과로 LCS의 길이와 LCS 자체를 출력합니다.문제 해결 코드#include #include using namespace std;int dp[1002][1002];stack s;int main() { string a, b; cin >> a >> b; int result = -1; // DP 테이블 채우기 for (int i = 0; i 0 && k > 0; i--) { ..

백준 7579번 [앱](C++) -yes6686- 티스토리 백준 문제 풀이: 7579 [앱]문제 링크: https://www.acmicpc.net/problem/7579문제 설명:여러 앱이 실행 중이며, 각 앱은 특정 메모리를 사용하고 있습니다. 메모리를 확보하기 위해 일부 앱을 종료해야 하는데, 이를 위해 앱마다 비용이 부과됩니다. 최소 비용으로 지정된 메모리 이상의 공간을 확보하려면 어떤 앱을 종료해야 할까요?문제 해결 코드#include using namespace std;int arrm[101]; // 앱의 메모리 사용량int arrc[101]; // 앱의 종료 비용int dp[10001]; // dp[j]: j 비용으로 확보 가능한 최대 메모리int sum[10001]; // 비용의 누적합int main() { int n, m; cin >> ..

백준 2098번 [외판원 순회](C++) -yes6686- 티스토리 백준 문제 풀이: 2098 [외판원 순회]문제 링크: https://www.acmicpc.net/problem/2098문제 설명:N개의 도시가 주어지고, 각 도시간의 이동 비용이 2차원 배열로 주어집니다. 1번 도시에서 출발하여 모든 도시를 한 번씩 방문한 뒤 다시 출발점으로 돌아오는 최소 비용을 구하는 문제입니다. 단, 이동할 수 없는 경우도 있을 수 있습니다.문제 해결 코드#include #include using namespace std;int arr[16][16];int dp[16][1 > n; for (int i = 0; i > arr[i][j]; } } memset(dp, -1, sizeof(dp)); cout 예제입력:40 10 15 2010 0 35 251..

백준 1562번 [계단 수](C++) -yes6686- 티스토리 백준 문제 풀이: 1562 [계단 수]문제 링크: https://www.acmicpc.net/problem/1562문제 설명:길이가 N인 계단 수는, 각 자릿수가 0부터 9까지 한 번씩 모두 포함되고, 자릿수 차이가 ±1인 수를 의미합니다. 주어진 N에 대해 계단 수의 개수를 구하는 문제입니다.문제 해결 코드#include #define mod 1000000000using namespace std;int dp[101][10][1 > n; // 초기값 설정: 첫 자리는 1부터 9까지 가능 for (int i = 1; i 예제입력:2출력:17코드 설명DP 배열: dp[i][j][t]는 길이가 i이고, 마지막 자리가 j이며, 비트마스크 t가 나타내는 숫자 상태(0~9 중 포함 여부)를 만족하는 계단..

이전 1 2 3 4 ··· 8 다음

728x90

LIST

티스토리툴바