본문 바로가기

Problem Solving/백준

 (80)
[백준/C++] 6549번 히스토그램 분할정복 증명 일단 그리디 하게 풀어서는 문제의 정답을 구할 수 없고, dp로 풀기에는 배열의 크기가 압도적으로 모자란 것으로 확인했다. HTML 삽입 미리보기할 수 없는 소스 그래서 분할 정복으로 왼쪽 오른쪽 나눠서 진행하면 어떨까? 하는 생각을 하게 되었지만, 각각 방향에서 최댓값은 찾을 수 있으나 다른 방향을 걸쳐서(가운데 부분에서) 최댓값을 구하는 경우면 어떻게 하나 고민하게 되었다. 고민 결과 아래와 같은 이유로 가운데가 포함된 경우 그리디 하게 모든 직사각형을 가져가는 것이 맞다고 생각하게 되었다. Prove 가운데가 포함된 직사각형에서 더 큰 방향의 막대를 포함하여 크기를 계산하면 최댓값을 구할 수 있다. Basis 가운데 막대가 포함된 경우에서 최댓값이 있다고 가정한다. 가운데를 제외한 왼쪽 부분의 최댓..
[백준/C++] 1744번 수 묶기 처음 문제를 읽고는 엥? 이게 왜 골드지...? sort하고 0이 아닌 양수 음수 각각 절대값이 큰 수부터 묶어나가면서 계산하면 되지 않나? 라는 생각을 하였다. (설마 출력이 2^31이라고 int 써서 통과 못하는 사람들이 생겨서 그런가 했다. 묶었을 때 2^31보다 커진 후 음수를 빼며 int 범위 내로 돌아갈 수 있는 걸 낚는 낚시인가 싶었다.) 운이 좋게도 예제 4번이 반례가 되어 -1 0 1 인 경우를 해결하지 못했다. 이 경우(-1 0) + 1 로 풀어야 하는데 내 알고리즘은 그렇지 못했다. 추가적으로 -5 -4 -1 0 5 10이라는 테스트 케이스를 생성한 후 고민해보았는데 양수 음수를 나눠서 양쪽으로 묶는 행위를 진행해야겠다 라는 생각이 들었다. 그런데 투 포인터로 설계하기에는 다소 어려움..
[백준/C++] 1700번 멀티탭 스케줄링 컴퓨터 구조 시간에 Memory Replacement Algorithm에 대해 배운 적이 있는데 그 때 LRU 등등 다양한 알고리즘을 배우다가 뒤에 올 것이 무엇인지 알면 가장 직후에 사용될 것을 찾는 방법이 optimal한 방법이라고 하였다. 그 때는 뒤에 어떤 것이 올지 알 수 없었지만 문제에서는 알 수 있으니 greedy하게 풀어낼 수 있을 것이라고 생각했는데 가지고 있는 것들 중에 더 일찍 재사용될 친구를 찾는다는게 생각보다 어려워서 숫자도 100으로 크지 않으니 queue를 각 아이템마다 만들어서 풀어내려고 하였다. 들어오는 순서대로 queue에 넣고 다음에 오는 숫자가 가장 느린 친구를 pop시켜주고 이미 가지고 있다면 continue 하는 방식으로 코드를 구현하였다. 코드를 구현할 때 이미 ..
[백준/C++/KOI] 2437번 저울 증명 및 풀이 문제를 처음 읽었을 때 dp라는 생각이 스쳐지나갔는데 100만개의 저울추가 1000까지의 숫자를 가지면 배열로 만들 수 없을만큼 큰 수가 되니 포기하고 1초라면 1억번 연산이니 최대 N log N 일 것이라고 생각하였다. sorting 한 번으로 구할 수 있다는 소리인데... 도저히 그리디로 풀 방법이 떠오르지 않아 질문 게시판의 도움을 얻으니 배열에서 다음에 오는 숫자가 기존 숫자들의 합보다 작으면 다음에 오는 숫자까지 더한 값까지 모든 수를 나타낼 수 있다 라는 힌트를 얻었고 이를 증명하고자 한다. Prove S(k) = ∑a[k] 이고 S(K)는 1 ~ S(K)까지 모든 수를 표현할 수 있을 때, S(k) + a[k+1]는 S[k] + a[k+1]까지 모든 수를 표현할 수 있다. Basis S(1)..
[백준/C++/KOI] 25381번 ABBC 문제를 처음 읽었을 때 그냥 그리디하게 풀면 되지 않나? 라는 생각이 들어 제한조건을 보니 S < 300000이었다. 2가지 지우는 방법을 모두 실행한다고 가정하여도 2 * 300000 이라 시간제한이 너무 널널해 잘못된 풀이인가? 하고 고민했다. 3초면 n logn 풀이가 있는 것인가 하고 고민하였는데 아무리 생각해도 그리디로 풀릴 것 같아서 편하게 짠 첫 코드는 5점을 맞았다. 처음 짠 코드는 2번 예제에 문제점을 해결할 수 있도록 뒤에서부터 C의 갯수를 세고 C의 앞에 B가 있다면 지워주는 방식을 생각했다. 지운 B의 위치를 bool로 체크해준 후 A를 세고 A의 앞에 B가 있다면 지우는 형식으로 짰었다. 틀린 이유를 고민하다가 발견한 반례는 BABC였다 CB를 먼저 지우면 A가 혼자 떨어지기 때문..
[백준/C++/KOI] 25378번 조약돌 풀이 모든 조약돌을 가져가는 최대 횟수는 2번 작업을 N번 반복하는 것이다. 그렇다면 1번 작업을 통해서 횟수를 줄여나갈 수 있는데 1번 작업으로 횟수를 줄이려면 인접한 장소의 조약돌을 모두 가져가는 경우일 것이다. (ex: [1, 1] [1 2 1]) 예시 5 2, 3, 6, 10, 5 왼쪽에서부터 차례로 모든 조약돌을 오른쪽에 있는 조약돌에서 같은 개수를 가져간다. 첫번째 돌부터 1번작업을 시작하는 경우 두번째 돌부터 1번작업을 시작하는 경우 ... 으로 경우를 나눌 수 있고 그렇게 0이 되는 순간 작업 횟수가 1번 줄어드는 것을 확인할 수 있다. 음수만큼 가져갈 수 없으니 이 경우 끊어준다. // This Code is written by gloryko fpqpsxh. 2 4 5 5 #include #i..
[백준/C++] 1005번 ACM Craft 이 문제를 처음 봤을 때는 최단경로 (Shortest Path)문제라고 생각하였습니다. 그래서 맨 뒤에서부터 각 Tree Level마다 걸리는 최대 시간을 찾아 return하면 되겠다고 생각하였습니다. 주어지는 간선(edge)를 거꾸로 받아서 출발하는 간선이 없는 노드(vertax)를 도착점으로 하면 되겠다고 생각하였으나, 교차되거나 복잡하게 꼬여있는 곳에서 오류가 생긴다는 것을 알게 되었고 왜 사용하지 못하는가에 자세한 사항은 아래 링크를 넣겠습니다. 아래 링크에 bfs, dfs,다익스트라, 재귀 등등 중요한 꿀팁이 들어있습니다. https://www.acmicpc.net/board/view/30959 글 읽기 - ★☆★☆★ [필독] ACM Craft FAQ ★☆★☆★ 댓글을 작성하려면 로그인해야 합니..
[백준/C++] 24268번 2022는 무엇이 특별할까? #include using namespace std ; int main() { int year, bits, value; cin >> year >> bits ; vector arr(bits); iota(arr.begin(), arr.end(), 0) ; while(next_permutation(arr.begin(), arr.end())) { if(arr[0] == 0) continue; value = 0; for(int i = 0 ; i year) { cout

티스토리툴바