전체 글74 [백준] 3321 - 가장 큰 직사각형 (c++) https://www.acmicpc.net/problem/3321 문제 요약0또는1로 이루어진 N*M크기의 행렬이 주어진다. 열끼리 순서를 바꿀 수 있을 때 1로 이루어진 직사각형의 최대 넓이를 구해라. 풀이 (NM)DP그리디밑변 행을 고정시켜 보자. 모든 열에 대해 높이를 내림차순 배열로 갖고 있으면 순회하며 (i*현재 높이)를 모두 구해 최대 넓이를 구할 수 있다.매번 퀵소트를 해주면 시간초과가 나기 때문에 O(N) 정렬 방식을 사용해야 한다. 직전 오름차순 배열에서 현재 값이 0이면 맨 뒤로 보내는 방법을 통해 정렬을 O(N)에 해결할 수 있다.#include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#defin.. 2025. 4. 29. [백준] 1762 - 평면그래프와 삼각형 (c++) https://www.acmicpc.net/problem/1762 문제 요약평면 그래프가 주어진다. 크기가 3인 사이클의 개수를 구해라. 풀이 (M)그리디평면 그래프라는게 중요하다. 완전 그래프 처럼 정점마다 간선이 많이 붙어 있는 형태면 시간초과를 피할 수가 없다. 하지만 평면 그래프는 이런 형태가 나올 수 없다. 간선이 많이 붙어있는 한 정점을 여러 번 방문하지 않도록 처리해주면 해결할 수 있다.#include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),v.rend()#define mid (st+en>>1)int main() { cin.tie(0)->sync_wi.. 2025. 4. 29. [백준] 11311 - Jug Hard (c++) https://www.acmicpc.net/problem/11311 문제 요약용량이 각각 a,b인 주전자 두개가 있다. 다음 동작들을 원하는 대로 반복해서 d만큼의 물이 든 주전자를 만들 수 있나?한 주전자에 물 가득 채우기한 주전자에서 다른 주전자로 남은 물 다 붓기 (나머지는 사라짐) 풀이 (logN)정수론d%gcd(a,b)==0을 만족하는 수만 모두 만들 수 있다.gcd(a,b) 아래론 만들 수 없다-> gcd(a,b)로 나뉘는 수는 만들 수 있다-> 나머지는 만들 수 없다.이런 순서로 직관에 의존 해 풀어야 한다. #include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#define rall(v) v.rbeg.. 2025. 4. 16. [백준] 22355- 말뚝 (c++) https://www.acmicpc.net/problem/22355 문제 요약N개의 말뚝이 일렬로 박혀있다. 말뚝마다 처음 높이, 높이를 높이는 비용, 높이를 낮추는 비용이 주어진다.연속한 K개 이상의 말뚝의 높이를 똑같이 만드는 데에 드는 비용의 최솟값을 구해라. 풀이 (NlogHlogH)세그먼트 트리삼분 탐색말뚝의 높이를 h로 만드는 데에 드는 비용을 그래프로 나타내면 아래로 볼록한 모양이다. 따라서 말뚝 구간의 높이를 h로 만드는데 드는 비용 그래프 또한 아래로 볼록하다. 삼분 탐색으로 최적의 높이를 구할 수 있다.각 말뚝의 높이를 h로 만드는 비용은 일차함수로 표현할 수 있는데 펜윅트리 두개로 여러 일차함수의 대한 쿼리를 처리할 수 있다. (계수를 관리하는 펜윅, 상수를 관리하는 펜윅)#inclu.. 2025. 4. 16. [백준] 22354 - 돌 가져가기 (c++) https://www.acmicpc.net/problem/22354 문제 요약돌 N개가 일렬로 있다. 각 돌의 색깔(흰색/검은색)과 무게가 주어진다. 자유롭게 돌을 가져갈 수 있고 인접한 두 돌의 색이 가져간 돌과 다르면 가져간 돌의 무게 만큼 점수를 얻는다.얻을 수 있는 최대 점수를 구해라. 풀이 (NlogN)그리디색이 같은 i~j그룹에서 점수를 얻을 수 있는 돌은 하나다. 그룹에서 최대 무게의 돌만 냅두고 다 주워주면 WBWBWB형태를 만들 수 있다. 양 끝 돌은 점수를 얻지 못하니까 유효한 돌은 (남은 돌-2)이다. 먹을 수 있는 돌의 개수는 항상 (유효한 돌+1)/2개 이고 어떤 집합을 선택해도 먹을 수 있는 경우의 수가 존재한다는 접근을 통해 그리디로 해결할 수 있다.#include using .. 2025. 4. 9. [백준] 24502 - blobsad (c++) https://www.acmicpc.net/problem/24502 문제 요약N개의 통을 나란히 있고 각 통에 있는 블롭 개수가 주어진다. 한 블롭을 인접한 칸으로 옮기는데 1초가 걸린다.모든 통의 블롭 개수를 K의 배수로 만드는데 걸리는 최소 시간을 구해라. 풀이 (N)그리디전체 블롭의 수가 K의 배수라면 i~j까지 구간의 블롭개수를 모두 K의 배수로 맞췄을 때 j+1~N의 블롭 수의 합이 K배수가 된다. 따라서 모든 i를 순회하며 {i,i+1} 쌍에서 어느 쪽으로 몇 마리 옮길지만 그리디하게 결정해줘도 된다. #include using namespace std;#define ll long long#define all(v) v.begin(),v.end()#define rall(v) v.rbegin(),.. 2025. 3. 27. 이전 1 2 3 4 ··· 13 다음