꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/4883 문제 정답률에 비해 쉬웠던 DP 문제였습니다.핵심은 4가지 방향을 고려해주는 문제였습니다: 오른쪽, 왼쪽 아래, 아래, 오른쪽 아래이 때, 범위를 벗어나는 경우 INF를 반환하게 하여 최소 비용을 찾게 해주면 쉽게 정답을 찾을 수 있는 문제였습니다.방심하고 문제 대충 읽다가 오른쪽을 고려안해서 정답률 하락에 보탬을 했던 것은 함정... #include #include #include //memset using namespace std; const int MAX = 100000; const int INF = 987654321; int N; int graph[MAX][3]; long long cache[MAX][3]; lon..

문제 링크입니다: https://www.acmicpc.net/problem/2666 벽장문의 이동 문제에서는 캐쉬에 변수가 세개가 필요합니다: 순서 인덱스, 열려있는 1번 문 인덱스 , 열려있는 2번 문 인덱스한번에 하나의 문을 이동하므로 두 가지 경우만 고려합니다.1. 1번 문을 이동하는 경우2. 2번 문을 이동하는 경우 이 때, 해당 순서 인덱스가 열려있는 문들의 인덱스보다 작을 수 있기 때문에 두 수의 뺄셈(이동 거리)를 절대값으로 처리해줘야합니다. #include #include #include //memsetusing namespace std; const int MAX = 20 + 1; int N, doorNum;int order[MAX];int cache[MAX][MAX][MAX]; //벽장 ..

문제 링크입니다: https://www.acmicpc.net/problem/2616 알고리즘 자체는 간단했습니다.1. 해당 칸을 끌고 가지 않거나2. 해당 칸을 최대 끌 수 있는만큼 끌고 간다. 그런데 여기서 간과한게 배열의 인덱스였습니다.계속 런타임 에러가 떠도 도저히 이유를 모르겠었는데 배열 인덱스 범위 초과 때문이라는 것을 깨닫고조건문에 if(idx + maxCarry - 1 = passengerCarNum) return 0; int &result = cache[trainNum][idx]; if (result != -1) return result; result = 0; //해당 객차를 끌고 가지 않을 경우 //해당 객차를 끌고 갈 경우 if(idx + maxCarry - 1 > passengerCa..

문제 링크입니다: https://www.acmicpc.net/problem/1652 처음에 문제를 이해하기 힘든 문제였습니다.제가 해석한대로 다시 문제를 말하자면 짐이 없는 열이면 누울자리가 많아도 한번만 추가합니다.그리고 짐을 기준으로 누울자리가 다시 생기면 그 때는 누울자리를 한번 더 추가해줍니다.(짐이 있는 곳 전에 충분한 공간이 있다는 가정) #include #include using namespace std; const int MAX = 100; int N; string room[MAX]; int maxRow(void) { int result = 0; for (int i = 0; i < N; i++) { int cnt = 0; for (int j = 0; j < N; j++) { if (room..

문제 링크입니다: https://www.acmicpc.net/problem/1789 1부터 순차적으로 더해나가야 N의 최대값을 찾을 수 있습니다.합이 S를 넘는 순간 마지막으로 더한 숫자를 수정하면 되므로 N의 최대값에서 1을 빼주면 정답이 됩니다. #include using namespace std; long long S; int maxN(void) { int num = 1; //1부터 더해나가야 N의 최댓값 int result = 0; long long sum = 0; while (1) { sum += num; result++; //합이 S를 넘기면 마지막에 더한 숫자를 수정하면 되므로 if (sum > S) { result--; //N의 최댓값을 하나 줄인다 break; } num++; } retu..

문제 링크입니다: https://www.acmicpc.net/problem/15483 Edit Distance 알고리즘 문제였습니다.간단하게 설명하기 위해 문자열 DOG와 SOL로 설명하겠습니다. 공백 D O G 공백 0 1 2 3 S 1 1 2 3 O 2 2 1 2 L 3 3 2 2 SOL을 기준으로 다음 과정을 설명하자면 (공백을 0으로 표현)i) 0a) 0->0: (0)b) 0->0D: D 삽입(1)c) 0->0DO: DO 삽입(2)d) 0->0DOG: DOG 삽입(3)ii) 0S a) 0S->0: S 삭제(1)b) 0S->0D: S->D 치환(1)c) 0S->0DO: S->D 치환 + O 추가(2)d) 0S->0DOG: S->D 치환 + OG 추가(3)iii) 0SO a) 0SO->0: SO 삭제..

문제 링크입니다: https://www.acmicpc.net/problem/1254 우선 이 문제를 푸는 방법은 두가지입니다.둘다 팰린드롬 여부를 확인하는 코드이지만 Manacher 알고리즘 개념을 적용하면 보다 간결한 알고리즘 작성이 가능해집니다.아래는 Manacher 알고리즘 개념을 알기 전에 작성한 코드입니다. #include #include using namespace std; string S;int length; int additionalLength(void){ int result = 0; for (int i = 0; i < length - 1; i++) { //양 끝이 같다면 if (S[i] == S[length - 1]) { //하나씩 땡기면서 양 끝을 확인 int start = i; int..

문제 링크입니다: https://www.acmicpc.net/problem/2864 알고리즘은 아래와 같습니다.1. 최대합을 구하고 싶을 때a) 각 자리수마다 쪼개서 해당 자리수가 5이면 6으로 바꿔주고b) 새로운 A와 B를 더해줍니다.2. 최소합을 구하고 싶을 때a) 각 자리수마다 쪼개서 해당 자리수가 6이면 5로 바꿔주고b) 새로운 A와 B를 더해줍니다. #include using namespace std; int A, B; //최대가 되려면 5가 모두 6이 되어야 한다 int maxSum(void) { int newA = 0, newB = 0; int copy = A; int multiplier = 1; while (copy) { int temp = copy % 10; if (temp == 5) t..

문제 링크입니다: https://www.acmicpc.net/problem/2624 거스름돈을 바꿔줄 때 해당 동전을 사용하지 않는 경우도 고려해야합니다.따라서 (0 ~ 해당 동전의 갯수)까지 모두 고려해야 맞출 수 있는 문제였습니다.#include #include #include //memset using namespace std; const int MAXCURRENCY = 10000 + 1; //0 < T = k) return 0; int &result = cache[cash][idx]; if (result != -1) return result; result = 0; //해당 동전을 사용하지 않는 경우 + i개 사용하는 경우 for (int i = 0; i = 0) result += numOfWays..

문제 링크입니다: https://www.acmicpc.net/problem/1328 3가지 경우의 수를 고려해야합니다.1. N-1 높이의 빌딩을 좌측과 우측을 제외한 곳에 추가하면 L과 R은 그대로입니다.2. N-1 높이의 빌딩을 좌측에 추가하면 L은 하나 증가합니다.3. N-1 높이의 빌딩을 우측에 추가하면 R은 하나 증가합니다. #include #include //memset using namespace std; const long long MOD = 1000000007; const int MAX = 100 + 1; //1 N >> L >> R; memset(cache, -1, sizeof(cache)); cout