[생각의 흐름] 1. 수열의 앞에서 부터 하나하나 더하면서 수열의 연속 된 특정 범위 내에서 K값을 찾는다. 2. 수열이 연속해야하기 때문에 맨 앞의 수열은 빼고 맨 뒤의 수열은 넣는 방법 두 가지가 있다. 3. K보다 값이 크면 맨 앞의 수열을 빼고(Pop) K보다 값이 작으면 맨 뒤에 수열을 추가한다(Push). 4. K와 값이 같으면 cnt++; * 맨 처음에는 수열(signal A)를 배열에 초기화 하여 사용하려 했으나 메모리 초과가 발생하여 그때 그때 값을 만들어 내는 방식을 택함. /* https://www.algospot.com/judge/problem/read/ITES */ #include #include #include using namespace std; const long MOD = ..
[생각의 흐름] 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. 전체 타일설치 경우의 수를 구한다. 2. 대칭인 타일설치 경우의 수를 구해서 뺀다. 3. 대칭인 타일의 경우의 수를 구하는 방법을 n이 짝수일때 홀수일때로 나눈다. 4. n이 짝수인 경우 다시 두가지 경우로 나눌 수 있는데 하나는 n/2로 대칭인 경우와 다른 하나는 전체 타일 가운데를 2x2타일을 배치한 뒤 절반으로 나누는 방법이다. (n-2)/2 n이 홀수인 경우는 자연스럽게 정가운데 타일 하나는 무조건 2x1타일을 배치해야 하기 때문에 (n-1)/2이 된다. 5. 타일의 경우의 수를 나눈 뒤 왼쪽 타일만 채워주면 모든 대칭 타일의 경우의 수를 구할 수 있다. 6. modulo연산에서 주의 할 점이 있는데 (전체 타일의 경우의 수 % MOD) - (대칭인 타일의 경우의 수 % MO..
[생각의 흐름] 1. 비오는날(75%)와 비가오지 않는날(25%)을 구분한다. 2. 비오는날과 비가오지 않는 날의 확률을 각각 곱하면서 목적지 (n)에 도달할 때까지 반복해 본다. => 완전탐색 3. 중복되는 경로의 확률을 메모이제이션 한다. 4. m일 안에 목적지 n에 도달했을 경우 1을 리턴하여 모든 경로의 확률을 곱하고 그렇지 않은 경우 0을 리턴하여 경우를 무효화 시킨다. 5. 절대 도달할 수 없는 경우( 예) 1000미터 우물을 100일 안에 도달)는 sol함수를 호출하지 않고 수식으로 가지치기 한다. /* https://www.algospot.com/judge/problem/read/SNAIL */ #include const int MAX_DAYS = 1001; const int MAX_MET..
[생각의 흐름] 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. 타일을 채우는 방법은 2개이다. 1) 세로로 채우는 방법 2) 가로로 채우는 방법 -> 결국 4X4타일이 됨 2. 타일을 n번째 까지 채웠을 때 그 이후 n+1 타일 부터 채우는 경우의 수를 개싱할 수 있다. #include #include const int MOD = 1000000007; const int MAX_TILE_SIZE = 111; int N; int cache[MAX_TILE_SIZE]; int sol(int n) { if(n == N) return 1; if(n > N) return 0; int &ret = cache[n]; if(ret != -1) return ret; // 타일을 세로로 쓰는 경우 + 타일을 가로로 2개 쓰는 경우 ret = (sol(n+1) % ..
[생각의 흐름] 1. 주어진 입력을 정렬하면 구현이 더 편해진다. 2. 정렬한 뒤 어떠한 기준에 따라 S개로 묶는다(양자화) 3. 어떠한 기준을 정의한다. -> a번째 부터 b번째 까지의 수열에 있는 모든 자연수 중 하나를 선택하여 오차 제곱의 합이 최소가 되는 값을 구한다. (minQuan 함수) /* https://www.algospot.com/judge/problem/read/QUANTIZE */ #include #include #include #include using namespace std; const int MAX_SEQ_SIZE = 111; const int MAX_QUAN_SIZE = 11; const int INF = 987654321; int N, S; int num[MAX_SEQ_S..
[생각의 흐름] 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. 수열A와 수열B의 LIS를 구해 더한다 -> 위와 같은 로직이면 예제 {10, 20, 30, 1, 2} {10, 20, 30} 일 때 정답은 {10, 20, 30}으로 JLIS의 길이는 3이됨 (정답은 5) 2. 수열A와 수열B의 중복 된 수를 한 쪽 수열에서 제거 한 뒤 각각 LIS를 구해 더한다. -> 문제의 예제에서 정답은 나오나 코드 제출 시 오답나옴 -> 중복이 제거되어도 1과 같은 수열 케이스가 나오면 오답 [생각의 흐름] - 정답 1. 수열A와 수열B의 모든 수를 따지면서 LIS를 구한다. -> "수열A의 수를 선택하거나 수열B의 수를 선택하거나"의 부분문제로 정의한다. 2. cache사용을 위해 계산의 중복이 있는지 찾아본다. -> 예를들어 {1, 5, 9, ..
