꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/5676 백준 11505번 구간 곱 구하기(http://jaimemin.tistory.com/816)와 동일한 문제였습니다. 문제에서는 쿼리의 결과의 부호만 궁금해하기 때문에 오버플로우를 방지하기 위해 배열을 입력 받을 때 양수면 1, 0이면 0, 음수면 -1을 입력해주면 됩니다. #include #include #include using namespace std; struct segmentTree { //배열의 길이 int n; //각 구간의 부분곱 vector pMult; segmentTree(const vector &array) { n = array.size(); pMult.resize(n * 4); init(array, 0..

문제 링크입니다: https://www.acmicpc.net/problem/11505 세그먼트 트리를 적절히 변형시켜주면 쉽게 구할 수 있는 문제였습니다.주의할 점은 모듈러 연산을 구간 곱을 구하는 함수 query와 구간을 업데이트하는 update 함수 내에서도 진행해줘야한다는 점입니다! #include #include #include using namespace std; const int MOD = 1000000000 + 7; struct segmentTree { //배열의 길이 int n; //각 구간의 부분곱 vector pMult; segmentTree(const vector &array) { n = array.size(); pMult.resize(n * 4); init(array, 0, n - ..

문제 링크입니다: https://www.acmicpc.net/problem/1275 전형적인 세그먼트 트리 문제였습니다.병렬 이분 탐색 문제를 풀려다가 세그먼트 트리와 펜윅 트리(혹은 BIT) 개념이 부족한 것 같아 먼저 구간트리 문제 내공을 다진 후 다시 시도하기로 마음을 먹었습니다. 세그먼트 트리 코드에 주석이 달려있기 때문에 이해하기 어려운 점은 없을 것입니다! #include #include #include using namespace std; struct segmentTree { //배열의 길이 int n; //각 구간의 부분합 vector pSum; segmentTree(const vector &array) { n = array.size(); pSum.resize(n * 4); init(arr..

문제 링크입니다: https://www.acmicpc.net/problem/15312 문제에서 요구하는대로만 구현하면 되는 간단한 문제였습니다.코드만 봐도 쉽게 이해할 수 있기 때문에 별도의 설명은 생략하겠습니다. #include #include #include using namespace std; //획 미리 저장 int stroke[26] = { 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 }; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 string A, B; cin >> A >> B; vector couple; //번갈아..

문제 링크입니다: https://www.acmicpc.net/problem/9663 전형적인 백트래킹 문제였습니다. 알고리즘은 아래와 같습니다.1. promising 함수를 통해 해당 칸에 퀸을 배치할 수 있는지 여부를 판단합니다.2. promising 함수가 true를 반환할 경우i) N 번째 열까지 도달했을 경우 완성된 체스판이므로 개수를 셉니다ii) 해당 열 모든 칸에 퀸을 배치하면서 가능성을 판단합니다다3. 총 완성된 체스판의 수를 출력합니다. #include using namespace std; int N, cnt; int col[15 + 1]; //배치 가능한지 여부 bool promising(int i) { int k = 1; bool flag = true; while (k < i && fl..

문제 링크입니다: https://www.acmicpc.net/problem/1167 백준 1967번 트리의 지름(http://jaimemin.tistory.com/531)과 동일한 문제였습니다.따라서 설명은 생략하겠습니다. #include #include #include #include //memset using namespace std; const int MAX = 100000 + 1; int V; bool visited[MAX]; vector graph[MAX]; int diameter = 0; int farthestNode = 0; void DFS(int node, int cost) { //기저 사례: 이미 방문한 곳 if (visited[node]) return; visited[node] = tr..

문제 링크입니다: https://www.acmicpc.net/problem/1315 스탯을 올릴 수 있는 포인트라는 개념이 있었기 때문에 상당히 까다로웠던 DP 문제였습니다. 알고리즘은 아래와 같습니다.1. 힘과 지능은 모두 1로 시작합니다.2. 현재 힘과 지능을 통해 깰 수 있는 퀘스트의 수를 구합니다.-> 이 때, 새로 클리어하는 퀘스트의 보상(포인트)의 누적합을 구합니다.3. 2번에서 구한 포인트의 누적합을 힘과 지능에 투자할 수 있는 모든 경우의 수를 고려하여 다시 재귀함수를 호출합니다.4. 3번에서 구한 퀘스트의 수 중 최대값을 반환합니다. #include #include #include #include using namespace std; const int MAX = 100 + 1; int N..

문제 링크입니다: https://www.acmicpc.net/problem/2675 간단한 문자열 문제였습니다.별도의 알고리즘을 요구하지 않는 문제이기 때문에 설명은 생략하겠습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 int test_case; cin >> test_case; for (int t = 0; t > R; string S; cin >> S; for (int i = 0; i < S.length(); i++) for (int j = 0; j < R; j++) cout

문제 링크입니다: https://www.acmicpc.net/problem/6064 최소공배수를 이용하여 푸는 문제였습니다. 알고리즘은 아래와 같습니다.1. 제한시간이 1초이며, M과 N이 40,000까지 주어질 수 있기 때문에 브루트 포스 형식으로는 풀 수 없는 문제였습니다.2. M, N의 최소공배수가 멸망년도입니다.3. 왼쪽에 주어진년도를 M으로 나누었을 때 x이여야하기 때문에 반복문 내에서 x에 M을 계속 더합니다.4. 3번을 반복하는데 주어진 y를 만족하는 년도를 찾거나 x가 멸망년도를 초과하면 반복문에서 탈출합니다.5. 멸망년도를 초과하면 -1을 출력하고 x, y를 만족하는 년도를 찾았다면 해당 년도를 출력합니다. #include #include using namespace std; int M,..

문제 링크입니다: https://www.acmicpc.net/problem/2292 주어진 그림을 보면 쉽게 풀 수 있는 문제였습니다. 규칙은 아래와 같습니다.a. 1번에서 시작합니다.b. 2~7은 2번에 걸쳐 갈 수 있습니다. (6)c. 8~19는 3번에 걸쳐 갈 수 있습니다. (12)d. 20~37은 4번에 걸쳐 갈 수 있습니다. (18)e. 38~61은 5번에 걸쳐 갈 수 있습니다. (24)... 결국, 범위가 6씩 증가하는 등차수열이기 때문에 반복문을 통해 간단하게 풀 수 있는 문제였습니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 int N; cin >>..