댄코 - 댄싱코딩

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

이름은 쉬운 계단수인데 전혀 쉽지 않았다. 처음에 1차원 배열안에 i자릿수로된 계단수의 갯수를 저장했는데 도저히 답이 안나와서 다르게 접근했다.#include using namespace std; ​ ​ ​ int main(){ int N = 0; int mod = 1000000000; int d[101][11]; scanf("%d",&N); for(int i = 1;i

이문제는 계단오르기 문제와 동일하게 생각했다가 아닌걸 깨닳았다.계단과 달리 이문제는 두칸을 뛰어넘을 수 도 있다.#include #include using namespace std; ​ int main() { int N = 0; int d[10001]; int a[10001]; scanf("%d", &N); ​ for (int i = 1; i

이문제는 처음에 이상한 점화식 세우다가 안돼서 다시푼 문제다.#include using namespace std; ​ int main(){ int N[2]; int val[101]; int d[10001] ={}; ​ scanf("%d %d",&N[0],&N[1]); ​ for(int i = 0;i