벨에삐

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://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 코딩 테스트 고득점 Kit에 포함된 Level 3 DP 문제입니다. #include #include using namespace std; const int MOD = 1000000007; int x, y, dp[101][101]; bool flag[101][101]; void init(vector& puddles){ for(vector puddle : puddles){ x = pudd..

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 코딩 테스트 고득점 Kit에 포함된 Level 3 DP 문제입니다. [BOJ] 백준 1932번: 정수 삼각형과 동일한 문제입니다. (https://www.acmicpc.net/problem/1932) #include #include #include using namespace std; int tri[501][501], dp[501][501], n; void init(vector& tr..

https://leetcode.com/problems/climbing-stairs/description/ Climbing Stairs - LeetCode Can you solve this real interview question? Climbing Stairs - You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example 1: Input: n = 2 Outpu leetcode.com 난이도 Easy로 상당히 쉬운 문제입니다. class Solution { publ..

https://leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode Can you solve this real interview question? Longest Increasing Subsequence - Given an integer array nums, return the length of the longest strictly increasing subsequence. Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest leetcode.com 정말 유명한 Longest Increasing S..

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