백준
-
[백준] 2900번: 프로그램 - C++개발/알고리즘 & PS 2024. 8. 27. 01:23
https://www.acmicpc.net/problem/2900 문제 구현을 그대로 구현하면 답을 얻을 수 있다. 하지만 시간복잡도가 굉장히 커지기 때문에 시간 초과를 받게 된다. something 함수를 호출 하는 과정에서 $O(KN)$, 합을 구하는 과정에서 $O(QN)$의 시간복잡도가 필요하다. 하지만 $N, K, Q$가 최대 $10^6$까지 커질 수 있으니 시간 제한을 만족시킬 수 없다. 구간 합구간의 합은 누적합을 사용하면 $O(1)$에 구할 수 있다. 따라서 누적합을 적용하면 $O(Q)$에 처리가 가능하다. something 호출매번 입력이 주어질 때마다 갱신하면 연산을 여러 번 반복하게 된다. 예를 들어 첫번째 원소는 항상 1씩 증가한다. 따라서 매번 업데이트 하지 말고 각 입력이 주어진 ..
-
[BOJ] 15970 화살표 그리기 - C++개발/알고리즘 & PS 2024. 4. 3. 22:30
https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 아이디어 같은 색의 점 중 가장 가까운 점을 찾아서 이으면 된다. 당연히 완전탐색으로는 시간을 맞출 수 없고 정렬을 이용하면 된다. (색, 위치) 순서로 저장해 정렬하면 같은 색끼리 원점에서 멀어지는 순서대로 모이게 된다. $n$번째 점에서 가장 가까운 점은 $n-1$번째나 $n+1$번째 점일 것이다. 코드 #include #include using namespace std; int ma..
-
[BOJ] 11508 2+1 세일 - C++개발/알고리즘 & PS 2024. 4. 1. 13:16
https://www.acmicpc.net/problem/11508 11508번: 2+1 세일 KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 www.acmicpc.net 아이디어 최소한의 값을 지불하려면 무료로 받는 제품의 가격을 최대한 크게 만들어야 한다. 다만, 무료로 받을 수 있는 제품은 3개 중 가장 싼 제품이기에 다른 두 제품이 비쌀수록 큰 할인을 받을 수 있다. 따라서, 내림차순으로 정렬한 후 3개씩 묶어 사면된다. 코드 #include #include using namespace std; int main() { cin.tie(nullptr)..
-
[BOJ] 20153 영웅이는 2의 거듭 제곱을 좋아해! - C++개발/알고리즘 & PS 2024. 3. 29. 23:27
https://www.acmicpc.net/problem/20153 20153번: 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해! 첫째 줄에 자연수 N (1 ≤ N ≤ 2,222,222)이 주어지고, 둘째 줄에는 N개의 자연수 A (1 ≤ A ≤ 2,222,222)가 주어진다. www.acmicpc.net 문제 해석 영웅이는 어떤 자연수 $A_n$을 2의 거듭제곱의 합으로 표현한다고 했는데 2진수로 나타내는 것과 같다. $A_n$ 중 최대 한 개의 자연수를 제외할 수 있다. 즉, 하나도 제외하지 않아도 된다. $2^x$가 홀수개면 $2^x$를 결과에 더한다. 즉, 2진수로 표현했을 때 1이 홀수개 존재하는 자리는 1, 짝수개라면 0이 되고 이 값의 최댓값을 찾아야 한다. 아이디어 ..
-
[BOJ] 14606 피자 (Small) - C++개발/알고리즘 & PS 2024. 3. 29. 14:08
https://www.acmicpc.net/problem/14606 14606번: 피자 (Small) 예제1의 입력이 1이므로, 게임 시작부터 갑이 분리할 수 있는 피자탑이 없습니다. 따라서 갑이 얻는 즐거움은 0입니다. 예제2의 정답 3은 다음과 같은 과정을 통해 얻어집니다. 먼저 놀이를 시작 www.acmicpc.net 아이디어 $n$개의 피자탑을 쪼갰을 때 가장 큰 즐거움을 얻으려면 짝수의 경우 $\frac{n}{2}$개, 홀수의 경우 $\frac{n}{2}$, $\frac{n}{2} + 1$개로 쪼개야 한다. 그리고 쪼개진 피자탑을 다시 쪼개서 $1$개가 될 때까지 얻을 수 있는 즐거움을 모두 더해주면 $n$개의 피자탑을 쪼갰을 때 얻을 수 있는 최대의 즐거움이다. $n$개의 피자탑을 쪼개 얻을 ..
-
[백준] 16985번 Maaaaaaaaaze C++개발/알고리즘 & PS 2023. 10. 19. 22:21
https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 3차원 BFS에 층별 재배치, 회전까지 들어가 있는 문제이다. 단순하게 모든 경우의 수에 BFS를 해보면 된다. 구현이 살짝 많다. 풀이 구상 층별 배열 순서를 결정한다. 각 층을 회전시킨다. BFS를 수행하고 최단거리를 구한다. permutation → 백트래킹 → BFS 순으로 알고리즘을 사용했다. next_permutation 각 층을 배열하는 경우의 수를 모두 구하려면..
-
[백준] 1062 가르침 C++개발/알고리즘 & PS 2023. 10. 18. 23:19
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 구상 모든 단어가 anta로 시작하고 tica로 끝나므로 a, n, t, i, c의 5글자는 무조건 배워야 읽을 수 있다. 저 5글자를 모두 배운 후 k - 5개의 글자를 추가로 배워 최대로 읽을 수 있는 단어의 개수를 세면 된다. 백트래킹을 활용하면 구현할 수 있다. k가 5보다 작은지 확인하고 작다면 모든 단어를 읽을 수 없으므로 0을 출력하고 종료한다. 또는, 모든 글자를 배울 ..