quant developer dave

미완성 #includeusing namespace std; int C,n,d,p;int g[51][51];int dp[101][101];double degree[101];int gogo(int here, int days){if(days == d){if(here==p)return 1;else return 0;} int &ret = dp[here][days];if(ret > -0.5) return ret; double ans = 0;for(int i = 0 ; i>C;while(C--){cin>>n>>d>>p;for(int i=0; ig[i][j];if(g[i][j]==1){degree[i]++;degree[j]++;}}}double v = -1.0;memset(dp,v,sizeof(dp)); } }

#includeusing namespace std; long long d[101][101]; int dp(int n, int first){if(n==first)return 1;if(nC;memset(d,-1,sizeof(d));while(C--){cin>>n;long long ans = 0;for(int first = 1; first

#include #include #include using namespace std; int d[3001][3001]; int s;string str;////int dp(int len, int s)//{////if(s==0)return 1;//if(s

#include #include #include using namespace std; int n,m;int C;bool areFriends[10][10],taken[10]; int countPairings(bool taken[10]){int firstFree = -1; for(int i=0; i>C;while(C--){memset(areFriends, false, sizeof(areFriends));cin>>n>>m;int f1,f2;for(int i=0; i>f1>>f2;areFriends[f1][f2] = true;areFriends[f2][f1] = true;}cout

#include #include using namespace std; void printPicked(const vector &picked){for(auto i = picked.begin(); i!=picked.end(); i++){cout

#include #include #include using namespace std; int color[220][220][220];int arr[30];const int C = 30;int sum;class node{public:int arr[3];int index;node(int a, int b, int c, int d){arr[0] = a; arr[1]=b;arr[2]=c;index=d;} bool operator rv) return true;else return false;}}; //bfsvoid seek(){queue q;q.push(node(0,0,0,0)); while(!q.empty()){node now = q.front();q.pop();if(now.index == C){cout

N*N 그리드에서 직선을 이루는 세 글자(트리플렛)의 개수를 구하는 문제다.처음에 가로, 세로, 대각선만 생각해 몇번 오답을 받았지만 모든 기울기의 직선을 다 구해야한다.그래서 모든 기울기에 대해 그리드를 순회하니 시간초과가 나왔다(n^5이니 .. 당연 ^^;;;)그 다음 생각한 방법은 희소 행렬을 만들어 푸는 방법이다. vector를 만들어서 세 점을 조합해 직선을 이루면 경우의 수에 추가하는 방법이다. 이런 방법으로 accept를 받았다. #include #include #include #include #include using namespace std; int main(){ int C,ans=0;string t[101];vector v;set s; cin>>C;for(int i=0; i>t[i];f..

dp(i,j) : (i,j)에서 시작해서 끝(m-1, n-1)까지 가는 경로의 합dp(i,j) = 인접칸 y,x(네 방향)의 dp(y,x)들의 합 (arr[i][j] > arr[y][x] 인 경우에만) #include #include using namespace std; int m,n,arr[501][501],cache[501][501];int func(int y, int x){if(y==m-1 && x == n-1) return 1;if(y>m-1 || x>n-1 || y arr[y-1][x]) count+=func(y-1,x);if(y arr[y+1][x]) count+=func(y+1,x);if(x>0 && std > arr[y][x-1]) count+=func(y,x-1);if(x arr[y][x..

주어진 수열에서 최장 등차수열을 찾는 문제이다. 최근에 푼 문제 중에서 제법 어려운 편인것 같다.일단 d[i][j]를 수열에서 i번째수와 j번째수로 시작하는 등차수열의 최대 길이로 잡았다. 이 발상을 하는데 혼자 고민을 한시간 넘게했다.그 후에 동적 계획법 함수 dp 안에서 first, second로 third를 찾는데 순차 탐색을 하니 전체 시간복잡도가 O(n^3)이 되어서 시간이 모자랐다. 시간 문제를 해결 하기위해 순차 탐색 대신에 이진탐색을 수행하였는데 여기서도 예외가 발생했다. 같은 수가 여러개 있는 상황을 고려하지 못했다. third가 될 수 있는 수가 여러개가 있다면 가장 왼쪽의 수를 선택해야한다. 이는 stl::low_bound 함수로 구현했다. d[first][second] : first..

한국정보올림피아드 지역본선 2009 초등부 5번 문제 숫자 맞추기 포스팅은 뜸하지만 꾸준히 하루에 여섯문제 일곱문제 이상은 풀어가고 있다. 간만에 재밌는 dp 문제를 풀어서 포스팅 한다. 처음 문제를 보고 든 생각은 bfs로 최단거리를 구하려했다. 하지만 자리 수 제한이 10000... 만 자리나 되는 숫자로 bfs 하기는 힘들어 보였고 점화식을 찾아 동적 계획법으로 풀었다. - 함수 int dp(int state, int add) - state번째 자리에서 시작하는 숫자에 add번 왼쪽으로 돌린 상태에서의 최소 회전 수 반환 - 구해야 하는 값 dp(0,0) - 점화식 1. 오른쪽으로 돌릴 때 : 오른쪽 회전은 밑에 다른 숫자에 영향을 주지 않고 자기 자신만 돌아간다. 따라서 점화식은 dp(state ..