벨에삐

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net dp 문제입니다. 다만, 가능한 이동방향이 "상하좌우"이므로 bottom-up 방식으로 탐색하기엔 어려움이 있습니다. 따라서 top-down 방식으로 구현하였습니다. #include using namespace std; int M, N, a[501][501], cache[501][501]; int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; int solve..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 백준 난이도 실버 2의 기본적인 dp 문제입니다. #include using namespace std; int N, M, board[1001][1001], dp[1001][1001]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i = 1; i board[i][j]; } } for(int i = 1; i

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 구간에 대한 쿼리를 처리하는 문제입니다. 전형적인 인덱스 트리, 세그먼트 트리 문제입니다. 모든 세그먼트 트리 문제는 indexed tree로 풀 수 있지만 그 역은 성립하지 않습니다. 따라서 indexed tree로 풀이합니다. #include #define ll long long using namespace std; const int SIZETR = 262144;..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [BOJ] 1149번 RGB 거리 문제에서 조건이 추가된 dp 문제입니다. 1번 집의 색과 N번 집의 색이 서로 같지 않아야 합니다. #include using namespace std; const int INF = 0x3f3f3f3f; int N, RGB[1001][3], dp[1001][3][3], ans; void solve(){ memset(dp, 0x3f, s..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 중학교 수준의 수학 지식이 필요한 DP 문제입니다. #include using namespace std; const int MOD = 10007; int N, K, dp[1001][1001]; void solve(){ for(int i = 1; i > K; solve(); } dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다. 1) table 정의 dp[i][j] : i choose j 2) 점화식 찾기 dp[i][..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 백준 10844번: 쉬운 계단수와 유사한 문제입니다. #include using namespace std; const int MOD = 10007; int N, res, dp[1001][10]; void solve(){ for(int i = 0; i

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 기본적인 DP 문제입니다. #include using namespace std; const int MOD = 1000000000; int N, dp[101][10], res; void solve(){ dp[1][0] = 0; for(int i = 1; i

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 기본 DP 문제입니다. #include using namespace std; int N, P[1001], dp[1001]; void solve(){ for(int i = 1; i P[i]; } solve(); } dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다. 1) table 정의 dp[i] : i개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 기본적인 DP 문제입니다. #include using namespace std; int N, dp[100001]; void solve(){ memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for(int i = 1; i = 1; --j){ dp[i] = min(dp[i], dp[i-j*j] + 1); } } cout > N; solve..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 기본적인 DP 문제입니다. #include using namespace std; const int MOD = 10007; int n, dp[1001]; void solve(){ dp[1] = 1; dp[2] = 3; for(int i = 3; i n; solve(); } dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다. 1) table 정의 dp[i] : 2×i 크기의 직사..