꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/5582http://jaimemin.tistory.com/370과 유사한 문제였습니다.LCS 문제 같은 경우 부분문자열이 연속하지 않아도 되지만 해당 문제는 연속하는 부분문자열이여야 했으므로 고려해야하는 부분이 추가되어 cache를 3차배열로 잡았습니다.현재 이어나가는 부분문자열이 존재하는지 여부를 판별하기 위해 bool head를 선언하였고 나머지는 LCS 문제와 똑같이 탐색을 진행하면 됩니다. #include #include #include #include using namespace std; const int MAX = 4000; string str1, str2; int cache[2][MAX][MAX]; int longes..

문제 링크입니다: https://algospot.com/judge/problem/read/GRADUATION비트마스크를 이용해 풀면 배열을 사용했을 때보다 훨씬 빠르게 풀리는 문제였습니다.비트마스크를 사용하면 배열의 단점인 삽입, 삭제 실행시간을 확실히 줄일 수 있습니다.예를 들어 과목을 삭제할 때는 canTake &= ~(1 50) exit(-1); for (int j = 0; j > majorNum >> required >> semesterNum >..

문제 링크입니다: https://www.acmicpc.net/problem/11049left~right까지 행렬을 곱했을 경우 최소 연산 횟수가 cache[left][right]에 저장되고 이를 2개의 부분문제로 바꾸는 것이 핵심이였습니다. #include #include #include //memset using namespace std; const int MAX = 500; const int INF = 987654321; int N; pair matrix[MAX]; int cache[MAX][MAX]; //left~right까지 연산하는데 드는 비용 int minCalc(int left, int right) { if (left == right) return 0; int &result = cache[l..

문제 링크입니다: https://www.acmicpc.net/problem/2169기존에 풀었던 DP 문제들은 오른쪽 혹은 아래만 갈 수 있어 재방문 여부를 확인하지 않아도 됬는데 해당 문제는 왼쪽도 고려해야했기 때문에 난이도가 다른 문제들보다는 있었던 문제였던 것 같습니다.visited[col][row]를 통해 방문 여부를 적절히 표시하는 것이 핵심이였습니다.(조합 구하는 재귀함수와 비슷) #include #include #include //memsetusing namespace std; const long long MININF = -2e9;const int MAX = 1000; int N, M; //세로 가로int Mars[MAX][MAX];bool visited[MAX][MAX];long long ..

문제 링크입니다: https://algospot.com/judge/problem/read/NERDS(신발 사이즈, 타이핑 속도)를 이차원 평면에 표시하고 너드인 그룹들과 너드가 아닌 그룹들 사이에 직선을 그을 수 있다면 이론이 성립함을 알 수 있습니다.다시 말해서 너드인 그룹 전부를 포함하는 볼록 다각형과 너드가 아닌 그룹 전부를 포함하는 볼록 다각형 사이에 교차 지점이 없을 경우 이론이 성립하고 교차지점이 있다면 이론이 성립하지 않습니다.볼록 다각형을 구하기 위해 선물 포장 알고리즘( https://en.wikipedia.org/wiki/Gift_wrapping_algorithm)을 사용했습니다. /*알고스팟에서 매년 진행하는 프로그래밍 대회가 가까워지고 있다.올해는 열기가 특히 뜨거워, 참가 신청자의..

문제 링크입니다: https://www.acmicpc.net/problem/5557왼쪽에서부터 차근차근 연산해가며 조건이 맞는지 확인하면 쉽게 풀 수 있는 문제였습니다. #include #include //memset using namespace std; const int MAX = 100; int N; int operand[MAX]; //피연산자 집합 long long cache[20 + 1][MAX]; //연산 결과인 0~20, idx long long numOfWays(int leftNum, int idx) //왼쪽에서부터 연산을 시작하므로 leftNum, idx는 여태까지 연산을 진행한 인덱스 { //기저 사례 if (leftNum 20) return 0; if (idx..

문제 링크입니다: https://www.acmicpc.net/problem/1495'계산 한적 없다'와 '불가능'한 경우를 다른 숫자로 표현하는 것이 핵심이였습니다.둘 다 -1로 표현한다면 메모이제이션이 정상적으로 처리하지 못하여 시간초과가 발생하기 때문입니다. #include #include #include //memset using namespace std; const int MAX = 100; const int MAXV = 1000; //최대 볼륨 int N, S, M; //곡의 수, 시작할 때 볼륨, 최대 볼륨 int playlist[MAX + 1]; int cache[MAXV + 1][MAX + 1]; int maxVolume(int volume, int idx) //현재 소리, 노래 번호 { ..

문제 링크입니다: https://www.acmicpc.net/problem/2240해당 시점에서 자리를 바꿀 경우와 그대로 있는 경우를 모두 고려하여 계산하면 답을 구할 수 있습니다. #include #include #include //memsetusing namespace std; const int MAX = 1000;const int MOVE = 30 + 1; int T, W;int plum[MAX];int cache[3][MAX][MOVE]; int maxPlum(int tree, int second, int move) //나무 번호, 초, 움직인 횟수{ //기저사례 if (second == T) return 0; int &result = cache[tree][second][move]; if (re..

문제 링크입니다: https://www.acmicpc.net/problem/9084http://jaimemin.tistory.com/362과 동일한 문제였습니다. /* 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모두 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. */ #include #include //memset using namespace std; const int MAX = 20; const int MONEY ..

문제 링크입니다: https://www.acmicpc.net/problem/11060간단한 메모이제이션을 이용하면 쉽게 풀 수 있는 문제였습니다.최대 arr[i]만큼 움직이는 것이므로 1부터 arr[i]만큼 움직여보는 것이 핵심이였습니다. #include #include #include //memset using namespace std; const int INF = 987654321; const int MAX = 1000; int N; int arr[MAX]; int cache[MAX]; int minJump(int start) { if (start == N - 1) //목적지 도달할 경우 return 0; if (start >= N) //목적지 도달 못할 경우 return INF; int &resul..