댄코 - 댄싱코딩

문제보기처음에 x,y를 y,x로 바꿔보겠다고 하다가 좌표가 엉켜서 여러번 틀렸었다. 좌표가 위아래가 바뀌어있어서 상하반전으로 생각하고 풀었다. 그 후 벡터에 첫좌표, 끝좌표, 아이템들의 좌표를 넣고 정렬해준 후 ,각 좌표 사이에 갈 수 있는 경로의 수를 DP로 구해서 전부 곱해주면된다. #include #include #include using namespace std;int map[101][101] = {}; int getLoadNum(pair n, pair m){ int dp[101][101]; int x1 = n.first; int y1 = n.second; int x2 = m.first; int y2 = m.second; //printf("position:%d %d %d %d\n",y1,x1,y2..

문제보기반복문을 돌면서 현재 위치(i)에서 전 번호들(j)의 수가 자신보다 작을때만 d[i] = d[j] + a[i] 이때 가장 큰 값을 d[i]에 저장해야하므로d[i] = max(d[i], d[j] + a[i]) #include using namespace std;int main(){ int N,res; int a[1001]; int d[1001] = {}; scanf("%d",&N); for(int i = 1;i a[j]){ d[i] = max(d[i],d[j] + a[i]); if(res < d[i]) res = d[i]; //printf("%d %d\n",i,d[i]); } } } printf("%d\n",res);}

https://www.acmicpc.net/problem/11057 계단수와 비슷하게 풀었다.d[i][j] 에서 i는 자릿수, j는 오르막수의 마지막 수를 뜻한다. 가령, d[1][2]는 마지막 수가 2인 1자릿수를 가진 오르막 수다. 만약 마지막 수가 1이라면 1~9가 뒤에 올 수 있다.만약 마지막 수가 2이라면 2~9가 뒤에 올 수 있다. 이런식으로 0부터 9(k)까지 반복문을 돌려 k >= j 일때 d[i][j] 에 d[i-1][k]를 모두 더해준다. 2017/07/01 - [코딩/알고리즘] - [10844] 쉬운 계단수 #include using namespace std; int mod = 10007; long upNumber(int N){ int d[1001][11] ={}; for(int i ..

2017/07/01 - [코딩/알고리즘] - [2293] 동전1 이문제는 동전1과 같은 문제라고 생각해서 그렇게 풀었는데 아니었다.동전1은 2+1과 1+2를 같다고 보지만,이문제는 두개를 다른 경우로 보기때문이다.사실 동전1에서두개의 포문 위치만 바꿔주면 된다. 구할 숫자에 대한 포문이 바깥이고 그 값을 1,2,3으로 만드는 경우의 수를 안쪽 포문으로 돌리면 중복은 고려치 않고 1,2,3값을 계속 d[j]에 추가해주기 때문이다. 동전1에서는 1,2,3으로 만드는 경우의수 포문이 바깥에 있었기때문에 중복없이 경우의 수를 구할 수 있었다. #include using namespace std; int main(){ int N, T = 0; int d[12]; scanf("%d", &T); for (int k ..

처음에 이진수 오타인줄 알았다. dp에 좀 더 익숙해 지기위해서 dp로 풀어보았다.한번 틀렸던게 N으로 90이 들어오면 int범위를 넘어간다. dp문제를 풀때는 자료형도 주의해야겠다.d[i][0]에는 i 번째 자릿수인 이친수의 끝자리가 0인 이친수,d[i][1]에는 i 번째 자릿수인 이친수의 끝자리가 1인 이친수를 저장했다. i번째 자릿수인 이친수의 끝자리가 1이려면 i-1자릿수인 이친수의 끝자리가 0이어야 한다.∴ d[i][1] = d[i-1][0] i번째 자릿수인 이친수의 끝자리가 0이려면 i-1자릿수인 이친수의 끝자리는 0또는 1이어야 한다.∴ d[i][0] = d[i-1][0] + d[i-1][1] 이 식을 1부터 N까지 돌리고d[N][0]과 d[N][1]을 더하면 N번째 자릿수인 이친수의 갯수가..

피보나치 수를 디피 탑다운 방식으로 풀어보았다.fibo 함수를 재귀로 부르면서 dp테이블에 값을 저장한다. 이때 dp[n]의 값이 이미 존재한다면 이전에 계산한 값이므로 dp[n]을 바로 리턴한다. 그렇지 않다면 n==0일때 0, n 0){ return dp[n]; } if(n == 0){ dp[n] = 0; }else if (n < 3){ dp[n] = 1; return 1; }else{ dp[n] = fibo(n-2) + fibo(n-1); } return dp[n];} int main(){ int N = 0; scanf("%d",&N); printf("%d\n",fibo(N));}

처음에 dfs로 풀었는데 당연하게도 시간초과가 떠서 dp로 생각하느라 오래걸렸던 문제다. 상,하,좌,우 네 방향을 전부 검사하면서 재귀로 값을 리턴받는다. 이렇게 이동한 후 끝지점에 도달했을 때 1을 리턴 받으므로 이동했던 경로(A)에 전부 1이 들어가게 된다. 그 후 다른 경로(B)로 이동하다가 전에 거쳤던 경로와 겹치게 되면 (D테이블의 값이 0보다 크면) 겹친 경로는 다시 가볼 필요없이 D테이블 값을 리턴해서 이동해온 경로(B)에 더해준다. 모든 경로를 거쳤을 때 d[0][0]에 갈 수 있는 경우의 수가 저장된다. #include using namespace std; int t[501][501];int d[501][501];int res;int downHill(int row, int col, int..

이 문제는 DP보다는 이전에 짰던 LCS1코드에 백트래킹을 사용해서 LCS값을 구하는 문제였다. 1.맨 오른쪽 아래에서 시작해서 d[i][j]값이왼쪽 --- d[i][j-1]왼쪽 위 --- d[i-1][j-1]위쪽 --- d[i-1][j]값들 보다 전부 크다면 결과스택에 N[i](첫 문장의 i번째 글자)를 push한다. 2.그 외의 경우 왼쪽값과 같으면 왼쪽으로 이동하고,3.그 외의 경우 위쪽으로 이동한다. i == 0 || j == 0까지 이동하면 스택에 LCS 값이 나와 top부터 차례대로 pop한다. #include #include #include #include #include using namespace std; int main(){ char N1[1001]; char N2[1001]; char..

이문제는 정답률이 27퍼센트라서 어려울것같았는데 의외로 두번만에 풀었다. 첫번째는 res변수를 0으로 초기화해서 최댓값을 구할때 음수가 나오면 처리가 안돼서 틀렸다. #include #include using namespace std; ​ int main(){ int N = 0; int a[100001]; int d[100001]; scanf("%d",&N); ​ int res = -10001; for(int i = 0;i res){ res = d[i]; } } printf("%d\n",res); }경우는 두가지이다.현재 숫자가 저번 숫자에 연속해서 더해지는 수 — d[i] = d[i-1]+[ai]현재 숫자가 첫번째로 선택된 수 — d[i] = a[i]둘중 최댓값을 넣으면 된다.그 후 d[i]중 최댓값을..

이 문제는 파보나치 수열과 비슷해서 매우 쉬웠다. 정답값이 int범위를 넘어가서 한번 틀려서 long long으로 고쳤다. 이제까지와는 달리 탑다운 방식으로 풀어보았다.#include using namespace std; ​ long long d[101]; long long padoban(long long n) { if (n