댄코 - 댄싱코딩

문제보기처음에 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..

문제보기붕어빵을 각 갯수 별로 한번에 판매할 수 있으므로,dp[i] = a[i]로 초기화를 해준다. i를 0부터 N까지 반복문 돌리면서 그안에서 j를 1부터 i-1까지 반복문을 돌리는데 그이유는 붕어빵을 살 수 있는 각 경우의 수 중 가장 큰 값을 도출하기 위함이다. 가령, i가 4이고 j가 1이라면 붕어빵 3개(i-j)를 팔면 남는 최대 수익(dp[i-j])에 붕어빵 1개(j)를 판 값을 더함i가 4이고 j가 2이라면 붕어빵 2개(i-j)를 팔면 남는 최대 수익(dp[i-j])에 붕어빵 2개(j)를 판 값을 더함i가 4이고 j가 3이라면 붕어빵 1개(i-j)를 팔면 남는 최대 수익(dp[i-j])에 붕어빵 3개(j)를 판 값을 더함 따라서 점화식은 다음과 같다. dp[i] = max(dp[i],dp[i..

문제보기반복문을 돌면서 현재 위치(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..