꾸준함

문제 링크입니다: 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

문제 링크입니다: https://www.acmicpc.net/problem/1016 처음에는 vector를 이용하여 풀었는데 중복된 제곱수를 추가하는 바람에 틀렸습니다.그래서 algorithm 헤더 파일을 추가하여 find 함수를 이용하여 중복된 제곱수를 방지했더니 시간 초과가 발생했습니다.따라서 언제나처럼 배열을 이용하여 풀었는데 한가지 유의사항은 인덱스를 0부터 시작하기 위해 arr[quotient*square - minNum]에 제곱수임을 표시해야한다는 점입니다. #include //#include //#include using namespace std; const int MAXSQRT = 1000000 + 1; long long minNum, maxNum; long long arr[MAXSQRT]..

문제 링크입니다: https://www.acmicpc.net/problem/1026 A를 내림차순으로 정렬하고 B를 오름차순으로 정렬한 뒤 각 인덱스마다 곱한 결과가 최소값입니다. #include #include #include using namespace std; int N; vector A, B; bool cmp(int num1, int num2) { return num1 > num2; } int minResult(void) { //A를 내림차순으로 정렬 sort(A.begin(), A.end(), cmp); //B를 오름차순으로 정렬 sort(B.begin(), B.end()); int result = 0; for (int i = 0; i < N; i++) result += (A[i] * B[i])..

문제 링크입니다: https://www.acmicpc.net/problem/1075 C/C++ 컴파일러에서는 나눌 때 무조건 내림한다는 것을 알고 있다면 쉽게 풀 수 있는 문제였습니다. #include using namespace std; int N, F; int getLast2Digit() { //100의 자리 시작 int start = (N / 100) * 100; int result; //마지막 두 자리만 비교 for (int i = start; i > N >>..

문제 링크입니다: https://www.acmicpc.net/problem/1967 처음에는 DP로 접근하여 cache, graph는 MAX*MAX 크기로 잡고 visited는 MAX 크기로 잡으니 메모리 에러가 발생했습니다. #include #include #include //memset using namespace std; const int MAX = 10000 + 1; int N; int graph[MAX][MAX]; bool visited[MAX]; int cache[MAX][MAX]; int getDiameter(int start, int node) { int &result = cache[start][node]; if (result != -1) return result; result = 0; f..