[생각의 흐름] 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. 비오는날(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. 타일을 채우는 방법은 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];..
