와이유스토리

10835번: 카드게임 (acmicpc.net) 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net #include #include #define N 2001 using namespace std; int n; vector l(N, 0); vector r(N, 0); int dp[N][N]; int func(int s, int e) { int& ret = dp[s][e]; if (ret != -1) return ret; if ((s >= n) || (e >= n)) return 0; ret..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net #include #include using namespace std; int n; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; vector board; vector dp; int func(int x, int y) { int& ret = dp[y][x]; if (ret != -1) return ret; ret = 1; for(int i=..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 메모이제이션 매개변수 대신 리턴값 사용 정렬 후 재귀 or LIS #include #include #include using namespace std; int n; int dp[101][501]; vector v; int func(int now, int before) { int &ret = dp[now][before]; if (ret != 1e9) return ret; if (now >= n) retur..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include #include #include using namespace std; /* (0,0) ~ (1,1) n 표시 -> 행별로 열 누적합 -> 열별로 행 누적합 [n, 0, -n, 0] [n, n, 0, 0] [n, n, 0, 0] [0, 0, 0, 0] [0, 0, 0, 0] [n, n, 0, 0] [-n, 0, n, 0] [-n, -n, 0, 0] [0, 0, 0, 0] */ int..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net dp[i][j] := i행의 1열부터 j열까지 배열 합 저장 ∴ (p,q)부터 (r,s)까지의 구간 합 : (dp[i][s]-dp[i][q-1])의 합 (i=p부터 r까지) #include using namespace std; int n, m, p, q, r, s, sum; int a[1025][1025]; int dp[1025][1025]; int ma..

※ 문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ※ 풀이 dp[i] := 1부터 i까지 배열 합 저장 ∴ i부터 j까지의 구간 합 : dp[j] - dp[i] (i

※ 문제https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net ※ 풀이- 초기화 dp[i]=1 (i=1부터 n까지)- dp[i] := max(dp[i], dp[j]+1) (수열[i] > 수열[j]) (i=2부터 n까지, j=1부터 (i-1)까지)∴ 1부터 n까지 dp 배열의 최댓값#include#define max(a,b) (((a)>(b))? (a) : (b))int main..

https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net #include #include #include #define MAX 10001 using namespace std; int n, a, b, ans; int dp[MAX][2]; int visited[MAX]; int check[MAX]; vector w; vector v[MAX]; vector tree[MAX]; vector r; void dfs(int x) { ..