꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2243 세그먼트 트리의 query 부분을 응용해야 풀 수 있는 문제였습니다.저는 아직 세그먼트 트리 개념이 부족했기 때문에 crocus님의 블로그를 참고하고 풀었습니다.(https://www.crocus.co.kr/668) 알고리즘은 아래와 같습니다.1. update 함수는 기존의 세그먼트 트리와 똑같습니다.2. 사탕의 수는 단말 노드에 있기 때문에 무조건 단말 노드로 향해야합니다.3. 왼쪽 자식으로 갈지 오른쪽 자식으로 갈지는 해당 노드에 사탕의 누적합이 K개 이상이냐 미만이냐에 따라 나뉩니다.i) 왼쪽 자식의 누적합이 K개 이상이면 왼쪽 노드로 가면 됩니다.ii) 왼쪽 자식의 누적합이 K개 미만이면 오른쪽 노드로 가고 (K ..

문제 링크입니다: https://www.acmicpc.net/problem/2023 에라토스테네스의 체 원리를 이용하는 문제이지만 메모리가 4MB 밖에 주어지지 않기 때문에 기존 문제들처럼 배열을 통해 소수를 판별하면 메모리 초과가 뜨는 문제였습니다. 따라서 아래와 같이 가지치기(pruning)을 해줘야합니다.1. 첫 번째로 등장할 수 있는 숫자는 2, 3, 5, 7 뿐입니다.2. 이 후에는 홀수만 등장할 수 있습니다.-> 짝수가 등장하면 신기한 소수의 조건을 만족하지 못합니다. #include using namespace std; int N; bool prime(int num) { if (num == 0 || num == 1) return false; for (int i = 2; i*i

문제 링크입니다: https://www.acmicpc.net/problem/2852 생각보다 까다로운 문제였습니다. 알고리즘은 아래와 같습니다. 1. 한 팀이 이기기 시작하는 시간을 start에 저장합니다. 2. 비기는 순간 해당 팀이 이기고 있었던 시간을 계산해서 더해줍니다. 3. 마지막에 한 팀이 이기고 있었을 경우 48분에서 start를 뺀 시간만큼 이기고 있었던 팀에 더해줍니다. 4. string 형식으로 출력해야지만 AC를 맞는 것 같습니다.(숫자를 integer 형식으로 제출하면 WA가 뜨는데 이유가 궁금하네요) 주의할 점은, 초의 범위는 0 이상 59 이하라는 것입니다. 해당 범위를 초과할 경우 1분을 더해주고 60초를 빼주고, 해당 범위보다 미만이라면 1분을 빼주고 60초를 더해줘야합니다...

문제 링크입니다: https://www.acmicpc.net/problem/10809 간단한 문자열 처리 문제였습니다. #include #include #include using namespace std; int visited[26]; int main(void) { string s; cin >> s; memset(visited, -1, sizeof(visited)); for (int i = 0; i < s.length(); i++) if (visited[s[i] - 'a'] == -1) visited[s[i] - 'a'] = i; for (int i = 0; i < 26; i++) cout

문제 링크입니다: https://www.acmicpc.net/problem/5624 A + B + C = D를 만족하는 D가 몇개 있는지를 물어보는 문제였습니다. 알고리즘은 아래와 같습니다.1. 문제를 A + B = D - C로 바꿉니다.2. D - C가 존재하는지 확인하고 존재한다면 좋은 수가 있다는 뜻입니다.3. 여태까지의 A + B를 표시합니다.4. 2번과 3번을 반복합니다. #include using namespace std; const int MAX = 5000; const int sumMAX = 400000; // -200,000 ~ 200,000 int A[MAX]; bool visited[sumMAX]; int main(void) { ios_base::sync_with_stdio(0); c..

문제 링크입니다: https://www.acmicpc.net/problem/1713 문제의 조건을 잘 읽고 그대로 코딩하면 되는 문제였습니다.조건이 5개나 되기 때문에 꼼꼼하게 잘 읽어보시는 것을 추천드리고 vector와 pair를 연습하기 좋은 문제였던 것 같습니다. #include #include #include using namespace std; const int MAX = 100 + 1; int recommend[MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; //{시간, 사진} vector v(N, { 0, 0 }); int rec; cin >> rec; for (int i = 0; i < rec..

문제 링크입니다: https://www.acmicpc.net/problem/12934 그리디하게 접근해야하는 문제였습니다. 알고리즘은 아래와 같습니다.1. x와 y의 합이 1 ~ K까지의 합이라면 가능한 경우이고 1 ~ K까지의 합이 아니라면 가능하지 않은 경우이니 -1을 출력해줍니다.2. 핵심은 K ~ 1까지 순회하면서 그리디하게 큰 수부터 빼주는 것입니다.-> 큰 수부터 빼준다면 덧셈의 횟수가 최소가 된다는 것은 자명합니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); long long x, y; cin >> x >> y; if (!x && !y) cout

문제 링크입니다: https://www.acmicpc.net/problem/11974 같은 학교 학우이신 Green55님 덕분에 풀 수 있었던 문제였습니다.이 문제는 푸는 방법을 알아야지만 쉽게 접근할 수 있었던 문제였던 것 같습니다. i > N; vector v[7]; //MOD 7 -> 0 ~ 6 int idx = 0; for (..

문제 링크입니다: https://www.acmicpc.net/problem/11973 모든 소를 하나 하나 터뜨려보면서 최대 연쇄폭파 횟수를 업데이트 해주면 되는 문제였습니다. #include #include using namespace std; const int MAX = 50000; int N, K; int hay[MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> K; for (int i = 0; i > hay[i]; sort(hay, hay + N); //폭파 범위 int range = 1; while (1) { int cnt = 0, idx = 0; while (1) { //K마리의 ..

문제 링크입니다: https://www.acmicpc.net/problem/11977 모든 소를 터뜨려보면서 최대 연쇄횟수가 몇 번인지를 확인하면 되는 문제였습니다. #include #include #include #include using namespace std; const int MAX = 100; int N, result; int hay[MAX]; bool visited[MAX]; void explode(int index) { queue q; //idx, range q.push({ index, 1 }); visited[index] = true; while (!q.empty()) { int idx = q.front().first; int range = q.front().second; q.pop();..