BOJ
-
[백준] 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씩 증가한다. 따라서 매번 업데이트 하지 말고 각 입력이 주어진 횟..
-
[백준] 27583번: Hunt the Wumpus - C++개발/알고리즘 & PS 2024. 8. 27. 01:09
https://www.acmicpc.net/problem/27583 영어 문제니 간단하게 요약해보면$10 \times 10$ 크기의 그리드에 4개의 Wumpus 가 있다.정수 $s$를 규칙에 맞춰 업데이트하고, 아래 2자리를 각각 $x, y$좌표로 삼는다.주어진 입력의 좌표로 이동했을 때 wumpus가 있다면 wumpus를 잡았다고 출력한다.가장 가까이 있는 wumpus의 맨해튼 거리를 (있다면) 출력한다.조심해 주어야 할 부분은 "The first four distinct numbers generated" 즉, $s$에서 wumpus의 위치를 만들 때 똑같은 위치가 나오면 안된다는 것이다.(당연한 건데 이걸 놓쳐서 정답률 100% 문제였는데 오답을 제출해 버렸다 ㅜㅜ). wumpus 위치 구하기$s$를..
-
[BOJ] 20365 블로그2 - C++개발/알고리즘 & PS 2024. 4. 7. 13:24
https://www.acmicpc.net/problem/20365 20365번: 블로그2neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한www.acmicpc.net 아이디어번갈아가며 나오는 색을 가장 적은 횟수로 칠해야 한다. 색을 다시 덧칠할 수 있음을 이용하면 된다. 연속해서 같은 색을 칠하는 부분을 하나로 생각하고 총 $m$개의 구역으로 나눌 수 있다고 하자. 빨간색과 파란색은 $\frac{m}{2}$내지 $\frac{m}{2} + 1$개의 구역을 가질 것이다. 첫 시도에 둘 중 많은 색을 칠하고 $\frac{m}{2}$번의 색을 칠하는 경우가 최소가 된..
-
[BOJ] 2143 두 배열의 합 - C++개발/알고리즘 & PS 2024. 4. 4. 11:28
https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그www.acmicpc.net아이디어두 수열 $A_n$, $B_m$의 연속한 원소들의 합을 $T$가 되도록 만들면 된다. 누적합을 통해 연속한 원소의 합을 빠르게 구할 수 있고 이분탐색을 통해 가능한 경우의 수를 빠르게 셀 수 있다. 부분합은 $1$부터 $i$까지의 합이고 이번 문제에서는 $i$부터 $j$까지의 합이 필요하므로 미리 나올 수 있는 모든..
-
[BOJ] 15970 화살표 그리기 - C++개발/알고리즘 & PS 2024. 4. 3. 22:30
https://www.acmicpc.net/problem/15970). 주어진 점들" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/15970" data-og-url="https://www.acmicpc.net/problem/15970" data-og-image="https://scrap.kakaocdn.net/dn/cqiasE/hyVJ7hmkbA/OR5E6rjpF7R1afl63zyEvK/img.png?width=2834&height=1480&face=0_0_2834_1480"> 15970번: 화살표 그리기직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른..
-
[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이 되고 이 값의 최댓값을 찾아야 한다.아이디어$A_n$을 각..
-
[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$개의 피자탑을 쪼개 얻을 수 있는..