이모저모

정수 삼각형이라는 문제이다. 오랜만에 알고리즘 문제를 풀어보니 c++을 다 까먹었다..... 머리가 너무 나쁜것 같다. 일단 문제는 아주 간단하며 풀이도 간단하다. 메모리는 O(N)이며 시간복잡도는 O(N^2)으로 풀 수 있다. 간단히 대각선 왼쪽 및 오른쪽에서 내려 올 수 있기 때문에 현재 위치가 i라면 i-1, i 중 큰 값을 가져오면된다. 점화식은 A[j][i] = max(A[j-1][i], A[j-1][i-1]) + input value (단 j는 j번째 줄 i는 그 줄의 i번째를 의미) 이렇게 보면 메모리가 N^2이여야 할것 같지만 이 전 값만 가지고 있으면 되기 때문에 2N으로 풀 수 있다. 아래는 풀이이다. 12345678910111213141516171819202122232425262728..

해결방법냅색 문제이다. 점화식dp[p][sum] : p-1까지 sum만큼 구했을 때 앞으로 목표 m에 정확히 도달하기 위한 최소 마나 값dp[p][sum] = min(dp[p+1][sum+life[p]]+mana)로 구해진다. 아래는 소스코드이다.#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef ..

해결방법다이나믹 프로그래밍이다.점화식dp[i][j] : [i,j]의 부분집합 중에서 팰린드롭의 갯수dp[i][j] = dp[i+1][j] (i를 포함하지 않는 경우) + dp[i][j-1] (j를 포함하지 않는 경우)- dp[i+1][j-1] (i,j 둘 다 포함하지 않는 경우(교집합이 발생하므로 빼준다.))+ str+i==str+j? dp[i+1][j-1]+1:0 (i,j가 같아서 i,j를 포함하는 경우 이때 +1하는 이유는 사이가 부분집합이 포함되어 있지 않으므로)시간 복잡도 O(n^2)초기 해결할때는 O(N^3)으로 풀었는데 풀이가 너무 복잡하여 시간복잡도를 줄인 방법으로 설명한다. 아래는 소스코드이다.#include #include #include #include #include #include ..

문제자체는 보자마자 DP인 것은 쉽게 유추가능했다. 하지만 점화식 세우는데 있어서 엄청나게 마니 틀렸다... 조금 더 점화식을 점검을하고 코딩을 해야하겠다.!!!! (조금 더 아트하게 점화식을 세우는 연습을 해야할듯) 코딩 실력 늘고 싶다. ㅜㅜㅜ 해결방법A[N] : 크기 3*N에서 (1,1)에서 (3,N) 까지 가는 경우의 수(문제의 요구 조건을 만족하는)B[N] : 크기 3*N에서 (2,1)에서 (3,N) 까지 가는 경우의 수(문제의 요구 조건을 만족하는)C[N] : 크기 3*N에서 (3,1)에서 (3,N) 까지 가는 경우의 수(문제의 요구 조건을 만족하는) 점화식A[N+1] = A[N]+B[N]+C[N] + C[N-1]+C[N-2]+.......+C[1]B[N+1] = A[N]+B[N]+C[N]C[..

해결방법다이나믹 프로그래밍dp[x][y] : x,y에 있을 때 먹을 수 있는 최대 사탕의 갯수dp[x][y] = max(dp[x+1][y], dp[x][y]) + current(x,y) 남아있는 사탕 갯수 아래는 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long l..

다이나믹 프로그래밍이다. 점화식 유도하는데 너무 오래걸렸다... 조금 더 연습을 해야 겠다. 아주 간단하게 구할 수 있는데 뻘짓을 한것 같다. 해결방법일단 파랑색을 고정시킨다.(파랑색을 칠하는 경우에 수는 N! 이며 각각의 경우에 대해 빨간색을 칠하는 경우의 수는 같게 나온다.) 기본 아이디어는 빨강색을 N*N을 칠할려면 (파랑색 N개는 칠해져 있다.)N-1개를 칠하면 나머지 하나는 자동적으로 정해지게 된다.이때 자동적으로(편하게 마지막 행이라 하자) 칠해지는 행에서의 파란색 위치에 N-1개에 중 꼭 하나는 빨간색이 칠해 져야한다.왜냐하면 마지막행의 파란색 위치에 열에 빨간색이 없다면 조건을 만족하지 않기 때문이다.위를 적용하면 아래와 같은 점화식이 만들어 진다.그림을 넣지 못해서 다소 아쉽긴 하지만 그..

점화식dp[pos][prev step] : 이전 스텝이 pre step 이고 현재 위치가 pos 일때 최대값dp[p][1] = dp[p-1][2] + data[p]dp[p][2] = max(dp[p-2][1], dp[p-2][2]) + data[p]나는 재귀형태로 그냥 풀었다. 소스코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#defi..

트리를 활용하는 dp 문제로 dp + dfs를 합쳐서 구현하면 된다. 점화식은for all childdp[parent][0] += max(dp[child][0], dp[child][1])dp[parent][1] += dp[child][0]최댓값은 0,1중에 선택하면 된다. 방문 정점을 찾고자 할 때는점화식을 구한 방식을 이용하여 최댓값을 선택한 루트부터 차례대로 tracking 을 하면 찾을 수 있다. 아래는 문제의 해결방법 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1..

시도1. dp[p][np][npp] : 현재 위치가 p일때 p+1 가 np만큼 움직였고, p+2가 npp만큼 움직인 상황에서 최소 횟수 p 위치에서 위 또는 아래로 1,2,3개를 같이 움직여서 p위치에 원하는 값을 맞추고 다음 p+1로 움직인다. 하지만 p 위치에서 1개를, 2개를, 3개를 조합해서 돌릴 경우가 존재할 수 있으며 위에는 그 경우의 수를 포함하지 않는다.해결방법dp[p][m1][m2][m3] : 위치가 p일때 p,p+1,p+2 위치에 대해 움직임이 m1,m2,m3 일때 최소 이동 횟수 위의 문제를 해결하기 위해 조합을 통해서 문제를 풀수 있게 바로 p+1로 움직이는게 아니라 1~9까지 움직여 보는 것이다. dp를 적용할 때는 모든 경우의 수를 포함할 수 있는지 꼭 점검해야 겠다.!!(물론 ..

BOJ 문제 https://www.acmicpc.net/problem/10272 해결방법시작점에서 끝점까지 순방향으로 가고 역방향으로 끝점에서 시작점으로 가야하기 때문에 다음과 같은 점화식이 성립한다.dp[p][bp] : 순방향의 위치가 p, 역뱡향의 위치가 bp 일때 이후 거리의 최솟값dp[p][bp] : min(dp[next][bp] + dist(p,next), dp[p][next] + dist(bp, next)) #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#de..