dp (21) 썸네일형 리스트형 [BOJ] 1516번 게임 개발 (C++) https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net #include #include #include using namespace std; int n; int cost[501]; vector edge[501]; int indegree[501]; int dp[501]; void topologicalSort(){ queue q; for(int i = 1; i > n; for(int i = 1; i > cost[i]; int input; cin.. [BOJ] 17090번 미로 탈출하기 (C++) https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net #include using namespace std; int n, m; char map[500][500]; int dp[500][500]; int answer; int dfs(int x, int y) { if (x = n || y = m) return 1; if (dp[x][y] != -1) return dp[x][y]; dp[x][y] = 0;.. [BOJ] 1520번 내리막길 (C++) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net #include using namespace std; int m, n; int map[500][500]; int dp[500][500]; int dx[4] = { -1, 0, 0, 1 }; int dy[4] = { 0, -1, 1, 0 }; int dfs(int x, int y) { if (x == m - 1 && y == n - 1) return 1; if (dp[x][y] != -1) ret.. [BOJ] 1563번 개근상 (C++) https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net #include #include using namespace std; const int divval = 1000000; int dp[1001][2][3]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; dp[1][0][0] = dp[1][1][0] = dp[1][0][1] = 1; for(int i = 2; i dp[n][0.. [BOJ] 5502번 팰린드롬 (C++) https://www.acmicpc.net/problem/5502 5502번: 팰린드롬 팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 www.acmicpc.net #include #include #include using namespace std; int dp[5001][5001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; string s, r_s; cin >> s; r_s = s; reverse(r_s.begin(), r_s.end()); for(int i = 1; i [BOJ] 12015번 가장 긴 증가하는 부분 수열 2 (C++) https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net #include #include using namespace std; int n; int arr[1000001]; vector seq; void binary_search(int num){ int low = 0, high = seq.size() - 1, mid; int ret = 1000000007; while(low = num){ if(ret > mid) ret = mid; high = mid -.. [BOJ] 11054번 가장 긴 바이토닉 부분 수열 (C++) https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net #include #include #include using namespace std; int n; vector arr(1001, 0); vector dp(1001, 1); vector r_dp(1001, 1); int main() { cin >> n; for(int i = 0; i > arr[i]; } for(int y = 0; y < n; y++){ for(int x = 0; x < y.. [BOJ] 2156번 포도주 시식 (C++) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net #include #include using namespace std; int arr[10010]; int dp[10010]; int n; int main() { cin >> n; for(int i = 1; i > arr[i]; } dp[1] = arr[1]; dp[2] = arr[1] + arr[2]; for(int i = 3; i 이전 1 2 3 다음
