[생각의 흐름] 1. 모든 경로(or 경우의수)를 완전 탐색 해본다. 2. 교도소의 인접한 마을(시작점)에서 탐색을 시작하는 경우 앞의 과정에서 계산한 확률 값이 필요하다. -> 까다로운 점 3. 시작점과 끝점을 뒤집어서 생각해 본다. 4. 끝점에서 시작해서 교됴소의 인접한 마을(시작점)으로 가는 경우만 구해서 확률을 계산한다. /* https://www.algospot.com/judge/problem/read/NUMB3RS# */ #include #include const int MAX_TOWN = 51; const int MAX_DAY = 101; int townMap[MAX_TOWN][MAX_TOWN]; double cache[MAX_DAY][MAX_TOWN]; int numOfConnectedTo..
[생각의 흐름] 1. 위에서 아래로 정사각형을 x개씩 채워나간다. 2. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 칸에 채우려는 사각형의 갯수를 알면 경우의 수를 구할 수 있다. ( 윗칸에서 채운 사각형의 수 + 현재 칸을 채우려는 사각형의 수 - 1) 3. 재귀함수를 통해 모든 경우의 수를 구한다. 4. 직전 윗칸에서 채운(사용한) 사각형의 갯수와 현재 사용할 수 있는 남은 사각형(leftBlock)의 갯수를 통해 메모이제이션이 가능하다. /* https://www.algospot.com/judge/problem/read/POLY */ #include #include const int MAX_BLOCK = 101; const int MOD = 10000000; int cache[MAX_BLOCK..
[생각의 흐름] 1. 최대 경로를 먼저 cache한다. (https://d-yong.tistory.com/107 와 동일) 2. 아래로 가는 경우 / 오른쪽 아래로 가는 경우 중 최대 경로가 큰 값을 경우의 수에 추가한다.(단, 두 값이 같은 경우 두 경우의 수를 모두 더한다.) /* https://www.algospot.com/judge/problem/read/TRIPATHCNT */ #include #include #include using namespace std; const int MAX_SIZE = 101; int n; int triangle[MAX_SIZE][MAX_SIZE]; int cache[MAX_SIZE][MAX_SIZE]; int cacheCnt[MAX_SIZE][MAX_SIZE]; ..
[생각의 흐름] 1. 문자열을 3, 4, 5개로 쪼갤 수 있기 때문에 재귀함수를 통해 모든 경우의 수를 구할 수 있다. 2. 1234123인 수를 쪼개는 방법은 3, 4 혹은 4, 3이다. 즉, 12341234가 N개 있으면 시간복잡도는 2^N이 된다. => 시간초과예상 3. 재귀함수가 현재 문자열의 position에 있을때 계산이 중복된다. => 메모이제이션 가능 /* https://www.algospot.com/judge/problem/read/PI */ #include #include #include using namespace std; const int INF = 987654321; const int MAX_LEN = 10001; char PI[MAX_LEN]; int cache[MAX_LEN];..
[생각의 흐름] 1. 완전 탐색으로 솔루션 도출 가능 (오른쪽이동 & 아래이동) 2. map의 각 포지션마다 메모이제이션 가능한 것을 파악 => 어떤 포지션이던 항상 결과는 동일 (참조적 투명성) /* https://www.algospot.com/judge/problem/read/JUMPGAME */ #include const int MAX_MAP_SIZE = 101; int n; int map[MAX_MAP_SIZE][MAX_MAP_SIZE]; int cache[MAX_MAP_SIZE][MAX_MAP_SIZE]; void init() { for (int i = 0; i < MAX_MAP_SIZE; i++) { for (int j = 0; j < MAX_MAP_SIZE; j++) { cache[i][j]..
