본문 바로가기

백준 문제 풀이

 (156)
[백준 2515번] 전시장 (C++) https://www.acmicpc.net/problem/2515 문제는 직관적으로 이해하기 어렵지 않았지만 어떻게 풀어야할지 감이 잘 안오는 문제다. 하지만 N = 30만이므로 완전탐색은 불가능하고 모든 그림을 배치하고 살펴보는 DFS, BFS 방식도 불가능하다고 판단했다. Greedy 탐욕법탐욕법은 어떨까? 그림의 가격순으로 정렬하고 가격이 높은 것부터 배치하고 다음 그림을 배치할 수 있다면 배치하는 방식을 사용하면 어떨까. 그리디를 사용하기 위해서는 두가지 조건을 만족해야한다.1. 탐욕 선택 조건: 앞에서 탐욕 선택한 값이 이후의 값에 영향을 주어선 안된다.2. 최적 부분 조건: 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다. 이 문제에서 탐욕 선택 조건에서 문제가 있다. 만약 100의 ..
[백준 1633번] 최고의 팀 만들기 (C++) https://www.acmicpc.net/problem/1633 1000개 중 30개를 적절히 구하는 것은 1000개중 30개를 뽑는 모든 연산을 진행해야한다. 1000 combination 30 = 2429608192173745103270389838576750719302222606198631438800 이다. 미친시간이 걸리기 때문에 완전탐색은 불가능하다.  탐욕법 (Greedy)그디리하게 접근해보자. 문제 조건처럼 총 30개를 선택하는 건 어려우니 백2, 흑2 총 4팀을 뽑는다고 가정하자.(10, 20), (30, 400), (5, 1000), (100, 10), (40, 40), (15, 30) 이렇게 들어올 때, 흑으로 정렬한다. (100, 10), (40, 400), (30, 40), (15,..
[백준 1484번] 다이어트 (C++) https://www.acmicpc.net/problem/1484 문제를 이해하기 힘들었다. 기억하고 있는 몸무게라니 이게 무슨말인지,, 그런데 질문게시판을 참고하고 문제를 몇번 다시 읽어보니 기억하고 있는 몸무게 = 이전 몸무게 였다. 1. beforeWeight + G = afterWeight2. afterWeight^2 - beforeWeight^2 = G 이 두 식으로 푸는 수학 문제라 생각했는데 여기서 G는 단순 차이가 아니라 새롭게 정의되어 있는 것이었다. 그러니까 1번 식은 잘못되었다. afterWeight는 a, beforeWeight 는 b라 할 때, 2번을 식을보면 G는 반드시 0보다 큰 자연수이기 때문에 a는 반드시 b보다 크다. 그리고 두 수를 선택해서 비교하는 작업은 두포인터가 가..
[백준 1241번] 머리 톡톡 (C++) https://www.acmicpc.net/problem/1241 이 문제는 순서가 있는 것 처럼 보이지만 사실은 순서가 전혀 중요하지 않은 문제이다. i번 숫자가 원을 돈다고 할 때 결국 지금 이 숫자가 내 약수인가? 라는 것이 문제이고 곧 이 숫자의 약수가 배열에 몇개가 있는가? 라는 것을 물어보는 문제이다. 그렇다면 시간복잡도 = O (약수를 구하는 시간 복잡도 * N) 으로 결정할 수 있다. 효율적으로 약수를 구하는 방법을 사용하면 O(Root(N)) 으로 해결할 수 있다.  36의 약수를 구한다고 해보자. 초등학생의 방법을 사용하면 1부터 36까지 모두 나누어보면 된다. 그렇다면 1, 2, 3, 4, 6, 9, 12, 18, 36 이 나온다. 벌써 느낌이 올 것이다. 19부터 35까지는 쓸대없는..
[백준] 13164번 행복유치원 (C++) https://www.acmicpc.net/problem/13164 N이 30만이기 때문에 모든 경우를 확인할 수 없는 문제이다. 이런 각 숫자들의 차이에 따라 갈리는 문제들은 각 숫자들의 차이를 위주로 생각해야한다. 5 31 3 5 6 10 예제 문제를 예로 들어보자. 1 3 | 5 6 | 10 이렇게 막대를 새우면(그루핑하면) 정답이다. 이걸 어떻게 찾을 수 있을까? 이번엔 각 숫자들이 이웃한 숫자와 차이를 적어보자 2 2 1 4 이 숫자는 곧 각 사이에 막대를 두었을 때 없앨 수 있는 비용과 같다. 즉 여기서는 3개로 나눌 수 있으므로 막대는 2개 새울 수 있으므로, 4와 2 위치에 막대를 두면 정답을 찾을 수 있다. 1 | 3 5 6 | 10 이렇게 해도 정답은 3이므로 같은 값이면 막대를 어디에..
[백준] 7573번 고기잡이 (C++) https://www.acmicpc.net/problem/7573 슬라이딩 윈도우같은 문제인데 사실은 브루트포스이다. 초등수준 도형 지식을 요구한다. 고기를 기점으로 왼쪽 사이드에 고기가 있다고 가정하고 브루트포스하면 되는 문제다. 단, 그물이 모든 바다를 덮을 수 있는 경우를 예외처리해야한다. 난 1만 * 1만 배열은 만들어 고기를 관리했는데 이렇게하면 메모리를 많이쓴다. 다른 사람들은 이렇게 안한것같다. 하지만 메인 로직은 같기 때문에 따로 참고하진 않았다.  #include#include#define MAX 10001using namespace std;int N, I, M;bool sea[MAX][MAX];vector> fishs(101);int fishing(int n, int m, int x, ..
[백준] 1461번 도서관 (C++) https://www.acmicpc.net/problem/1461 문제세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.입력첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다..
[백준] 과일 탕후루 (C++) https://www.acmicpc.net/problem/30804 양 끝에서 숫자를 빼가며 Greedy 한 방법으로는 문제를 풀 수 없다. 그리고 N = 20만이기 때문에 양옆에서 빼는 모든 방법을 해보는 것은 불가능하다. 그러므로 두포인터를 활용해 범위를 계속 갱신해가며 풀어야하는 문제이다.  기본 예제로 시뮬레이션해보자. Lo는 첫번째 원소를, hi는 두번째 원소를 가리키고 있다. 이 때 탕후루의 종류는 5, 1 로 총 2개이고 길이는 2이다. 이제 hi를 1 늘려서 보자. 아직 종류가 2개이다.   범위를 더 늘렸더니 종류가 3개가 되었다. 그러므로 이제 범위를 줄여야한다. lo를 하나 늘리자  이제 정상화 되었으므로 hi를 하나 늘린다.   hi가 끝까지 왔으므로 더이상 탐색하지 않아도된다. l..

티스토리툴바