꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/11333 규칙을 찾아서 재귀함수로 해결하고 싶었지만 역량이 부족했습니다.결국 stackoverflow(https://stackoverflow.com/questions/22191801/given-an-integer-n-in-how-many-ways-can-we-tile-a-4-x-n-rectangle-with-3-x-1-ti)에서 점화식을 참고하여 풀 수 있었습니다. *이런 문제는 규칙을 찾아서 점화식 세우는 것 밖에 답이 없는지 궁금합니다. #include using namespace std; const int MAX = 10000; const long long MOD = 1000000007; long long cache[MAX..

문제 링크입니다: https://www.acmicpc.net/problem/11058 CtrlA + CtrlC + CtrlV를 한 뒤에는 복사한 문자열을 다시 붙여넣을 때 (CtrlA + CtrlC)를 누를 필요없이 CtrlV만 눌러도 된다는 부분만 이해했다면 쉽게 풀 수 있는 문제였습니다. #include #include #include using namespace std; const int MAX = 100 + 1; int N; long long cache[MAX]; long long func(int idx) { long long &result = cache[idx]; if (result != -1) return result; result = 1 + func(idx - 1); //A 추가 //Ctrl..

문제 링크입니다: https://www.acmicpc.net/problem/2568 백준 2565번 전깃줄(https://jaimemin.tistory.com/1094)의 연장선 문제였습니다. 알고리즘은 아래와 같습니다.1. 연결한 줄을 입력받고 A 전봇대 인덱스를 모두 visited 배열에 표시합니다.2. LIS 함수를 통해 가장 긴 부분 증가 수열의 길이를 구합니다.-> answer 배열에 {인덱스, 연결된 B 전봇대 인덱스} 표시해줍니다.3. N - (2번에서 구한 길이)를 출력해줍니다.4. 각 인덱스에 위치한 A 전봇대 인덱스를 구하고 해당 인덱스는 연결이 되어있는 상태이므로 visited 배열에서 빼줍니다.5. 4번까지 완료하면 visited 배열에 표시되어있는 인덱스는 초기에는 연결했지만 LI..

문제 링크입니다: https://www.acmicpc.net/problem/14002 가장 긴 증가하는 부분 수열 5(https://jaimemin.tistory.com/1095)와 동일한 문제였습니다. #include #include #include using namespace std; const int MAX = 1000 + 1; int N; int arr[MAX]; int cache[MAX]; pair answer[MAX]; stack s; int LIS(void) { int idx = 0; cache[idx] = arr[0]; answer[0] = { 0, arr[0] }; for (int i = 1; i < N; i++) { if (cache[idx] < arr[i]) { cache[++idx]..

문제 링크입니다: https://www.acmicpc.net/problem/14003 Crocus님(https://www.crocus.co.kr/681) 덕분에 풀 수 있었던 문제였습니다.O(NlogN)에 LIS의 최대 길이를 구하는 알고리즘을 통해서는 정확한 LIS 배열을 구할 수 없다는 것을 처음 알았습니다. 기존의 LIS 코드는 동일하고 pair answer 배열과 스택을 이용해 정확한 LIS 배열을 구하는 것은 코드의 주석을 보면 이해가 될 것입니다! #include #include #include using namespace std; const int MAX = 1000000 + 1; int N; int arr[MAX]; int cache[MAX]; pair answer[MAX]; stack s..

문제 링크입니다: https://www.acmicpc.net/problem/2565 백준 2352번 반도체 설계(https://jaimemin.tistory.com/488)와 유사한 문제였습니다. #include #include using namespace std; const int MAX = 500 + 1; int N; pair connect[MAX]; int cache[MAX]; int LIS(void) { int idx = 0; int length = 0; cache[idx] = connect[0].second; for(int i=1; i> N; for (int i = 0; i > connect[i].first >> connect[i].second; sort(connect..

문제 링크입니다: https://www.acmicpc.net/problem/5015 Algospot Wildcard(https://jaimemin.tistory.com/315)와 동일한 문제였습니다. #include #include #include #include #include using namespace std; const int MAX = 100 + 1; int N; string P, S; int cache[MAX][MAX]; int func(int pIdx, int sIdx) { int &result = cache[pIdx][sIdx]; if (result != -1) return result; //둘이 일치하면 if (pIdx < P.size() && sIdx < S.size() && P[pId..

문제 링크입니다: https://www.acmicpc.net/problem/2253 오랜만에 다이나믹 프로그래밍 문제였습니다. 알고리즘은 아래와 같습니다.1. N의 범위는 최대 10000이고 M의 범위는 대략 log(N) + α 이기 때문에 캐시 배열을 [10000+1][250] 정도로 잡아줬습니다.-> (k)(k+1)/2 N >> M; for (int i = 0; i > num; rock[num] = true; } memset(cache, -1, sizeof(cache)); int result = jump(1, 0); if (success) cout

문제 링크입니다: https://www.acmicpc.net/problem/1660 언제나처럼 Top-Down 방식으로 접근했지만 메모리 에러가 발생했습니다.접근 방법은 Bottom-Up 방식과 유사하게 했지만 재귀호출을 너무 많이 하여 오류가 뜨는 것 같습니다. #include #include #include //memset using namespace std; const int MAX = 300000 + 1; //cannon[121] = 302621 const int CANNONMAX = 121 + 1; int N; int cannon[CANNONMAX]; int cache[MAX]; void preCalculate(void) { //사면체 각 줄에 필요한 대포 개수 구하고 for (int i = 1..

문제 링크입니다: https://www.acmicpc.net/problem/1562 계단수의 대한 개념은 http://jaimemin.tistory.com/359?category=988050(쉬운 계단수)를 통해 익혀놓았기 때문에 쉽게 접근할 수 있었던 문제였습니다.하지만 이 문제에서는 10844번과 다르게 0~9 모두 등장해야 계단수라고 여깁니다. 처음에 문제를 풀었을 때는 접근 방법은 맞았지만 메모이제이션 시 0~9가 사용되었는지 표기하는 배열을 고려안해서 틀렸습니다.아래는 제가 처음에 작성한 코드입니다. #include #include //memset using namespace std; const int MAX = 100 + 1; const int MOD = 1000000000; int N; in..