BAEKJOON/다이나믹 프로그래밍 (58) 썸네일형 리스트형 백준 1005번 [ACM Craft](C++) -yes6686- 티스토리 백준 문제 풀이: 1005 [ACM Craft]문제 링크: https://www.acmicpc.net/problem/1005문제 설명:건물 건설 순서와 각 건물의 건설 시간을 이용해 특정 건물 완공까지 걸리는 최소 시간을 계산하는 문제입니다.각 건물은 선행 건설 조건을 가집니다.선행 조건이 충족된 후 해당 건물을 건설할 수 있습니다.특정 건물 W를 완성하는 데 필요한 최소 시간을 구해야 합니다.문제 해결 코드#include #include #include #include using namespace std;vector v[1001];queue q;int arr[1001];int dp[1001];int len[1001];int main() { ios_base::sync_with_stdio(false).. 백준 17070번 [파이프 옮기기 1](C++)-yes6686- 티스토리 백준 문제 풀이: 17070 [파이프 옮기기 1]문제 링크: https://www.acmicpc.net/problem/17070문제 설명:크기 NxN의 격자판에서 파이프를 이동시키며 (1, 1)에서 (N, N)으로 이동할 수 있는 모든 경로의 개수를 구하는 문제입니다. 파이프는 항상 격자판 위에 존재하며, 빈 칸(0)만 이동할 수 있습니다.파이프의 이동은 다음 규칙을 따릅니다:파이프는 세 가지 방향(가로, 대각선, 세로)으로 이동 가능합니다.가로 방향(1)에서는 오른쪽 또는 대각선으로만 이동 가능합니다.대각선 방향(2)에서는 세 방향 모두(오른쪽, 아래, 대각선) 이동 가능합니다.세로 방향(3)에서는 아래 또는 대각선으로만 이동 가능합니다.대각선 이동 시, 이동할 칸과 그 주변 두 칸이 모두 비어 있어야.. 백준 21600번 [계단](C++)-yes6686- 티스토리 백준 문제 풀이: 21600 [계단]문제 링크: https://www.acmicpc.net/problem/21600문제 설명:주어진 배열에서 "계단"의 정의를 만족하는 가장 긴 부분 배열의 길이를 구하는 문제입니다. 계단의 정의는 다음과 같습니다:각 원소는 이전 원소보다 작거나 같아야 하며, 동시에 각 원소는 해당 계단에서 선택 가능한 최대 높이를 넘지 않아야 합니다.입력:첫째 줄에 배열의 길이 n이 주어집니다. (1 ≤ n ≤ 100,000)둘째 줄에 길이 n의 정수 배열 arr가 주어집니다. (1 ≤ arr[i] ≤ 100,000)출력:계단의 정의를 만족하는 가장 긴 부분 배열의 길이를 출력합니다.문제 해결 코드#include #include using namespace std;int arr[1000.. 백준 1890번 [점프](C++)-yes6686- 티스토리 백준 문제 풀이: 1890 [점프]문제 링크: https://www.acmicpc.net/problem/1890문제 설명:n × n 크기의 게임판이 주어집니다. 각 칸에는 수가 하나 적혀 있으며, 이 숫자는 그 칸에서 점프할 수 있는 거리입니다. (오른쪽 또는 아래쪽으로만 점프 가능)맨 왼쪽 위에서 출발하여 맨 오른쪽 아래까지 도달하는 방법의 수를 구하는 문제입니다.입력:첫째 줄에 n (4 ≤ n ≤ 100)이 주어집니다.둘째 줄부터 n개의 줄에 걸쳐 게임판의 정보가 주어집니다. 각 칸의 숫자는 0 이상 9 이하의 정수입니다.출력:맨 왼쪽 위에서 출발하여 맨 오른쪽 아래로 도달하는 방법의 수를 출력합니다.문제 해결 코드#include using namespace std;long long dp[101][1.. 백준 12865번 [평범한 배낭](C++)-yes6686- 티스토리 백준 문제 풀이: 12865 [평범한 배낭]문제 링크: https://www.acmicpc.net/problem/12865문제 설명:n개의 물건이 있고, 각 물건은 무게와 가치가 있습니다. 최대 k 무게를 담을 수 있는 배낭에 물건을 담을 때, 최대 가치를 구하는 문제입니다.입력:첫째 줄에 정수 n (1 ≤ n ≤ 100)과 k (1 ≤ k ≤ 100,000)이 주어집니다.다음 n개의 줄에는 각각 물건의 무게 w (1 ≤ w ≤ k)와 가치 v (0 ≤ v ≤ 1,000)가 주어집니다.출력:첫째 줄에 배낭에 담을 수 있는 물건들의 가치합의 최댓값을 출력합니다.문제 해결 코드#include #include using namespace std;int n, k;int weight[101];int value[1.. 백준 11660번 [구간 합 구하기 5](C++)-yes6686- 티스토리 백준 문제 풀이: 11660 [구간 합 구하기 5]문제 링크: https://www.acmicpc.net/problem/11660문제 설명:2차원 배열에서 특정 구간의 합을 구하는 문제입니다. 입력된 행렬에서 여러 쿼리에 대해 지정된 좌표 범위의 합을 효율적으로 계산해야 합니다.입력:첫째 줄에 정수 n과 m이 주어집니다. (1 ≤ n ≤ 1,024, 1 ≤ m ≤ 100,000)다음 n개의 줄에는 행렬의 원소가 주어집니다. 행렬의 원소는 1,000 이하의 자연수입니다.이후 m개의 줄에는 네 개의 정수 x1, y1, x2, y2가 주어집니다.출력:각 쿼리에 대해 지정된 좌표 구간의 합을 한 줄에 하나씩 출력합니다.문제 해결 코드#include using namespace std;int arr[1025][1.. 백준 11054번 [가장 긴 바이토닉 부분 수열](C++)-yes6686- 티스토리 백준 문제 풀이: 11054 [가장 긴 바이토닉 부분 수열]문제 링크: https://www.acmicpc.net/problem/11054문제 설명:바이토닉 수열은 부분 수열의 길이가 증가했다가 감소하는 특징을 가집니다. 주어진 배열에서 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제입니다.입력:첫째 줄에 배열의 크기 n이 주어집니다. (1 ≤ n ≤ 1,000)둘째 줄에 배열의 원소가 주어집니다. (1 ≤ 원소 값 ≤ 1,000)출력:가장 긴 바이토닉 부분 수열의 길이를 출력합니다.문제 해결 코드#include #include using namespace std;int arr[1001];int inc[1001]; // 증가 부분 수열int dec[1001]; // 감소 부분 수열int main() {.. 백준 9251번 [LCS](C++)-yes6686- 티스토리 백준 문제 풀이: 9251 [LCS]문제 링크: https://www.acmicpc.net/problem/9251문제 설명:두 문자열 A와 B가 주어질 때, 두 문자열의 최장 공통 부분 수열 (LCS)의 길이를 구하는 문제입니다. 최장 공통 부분 수열은 두 문자열에서 순서를 유지하며 일부 문자를 선택하여 만들 수 있는 가장 긴 부분 수열입니다.입력:첫 번째 줄에 문자열 A가 주어집니다.두 번째 줄에 문자열 B가 주어집니다.문자열의 길이는 최대 1,000입니다.출력:첫 번째 줄에 두 문자열의 LCS 길이를 출력합니다.문제 해결 코드#include #include #include using namespace std;int dp[1001][1001];int main() { string a, b; c.. 이전 1 2 3 4 5 ··· 8 다음