본문 바로가기

PS/BOJ57

백준 2805 / C++ https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색(파라매트릭 서치) 입문문제이다. 설명은 코드로 대체. [ 코드 ] #include using namespace std; using ll = long long; ll n, m, h[1000001]; // 높이 x로 자른 나무들의 합이 m이상인지 판별하는 함수 int check(ll x) { ll sum = 0; for (int i = 0; i < n;.. 2022. 7. 15.
백준 16118 / C++ https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net [ 풀이 ] 여우는 v로 가고 늑대는 2v v/2 를 반복한다. 이 때 시간은 여우는 d/v , 늑대는 2d/v 또는 d/2v가 걸린다. 모두 정수로 맞춰주면, 시간은 여우가 2t 2t .... 늑대는 t / 4t / t / 4t .. 이렇게 걸린다. 여우의 경우 그냥 다익을 돌려주면 최단시간이 나온다. 늑대의 경우가 이 문제의 핵심이다. .. 2022. 7. 15.
백준 1062 / C++ https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [ 풀이 ] anta와 tica는 디폴트로 가르쳐야 한다. 이 5개를 제외한 글자를 가르치자. 알파벳이 26개이니 그냥 브루트포스로 21C(k-5)개를 골라주면 된다. k-5개를 골라 가르친 후에 N개의 문자열을 읽을 수 있는지 확인해주면 된다. sol 1) 그냥 모든 문자열을 순회하며 읽을 수 있는지 판별한다. 총 시간복잡도는 O(21Ck-5 * N*15)이고 이 값의 최대는 대충 21C.. 2022. 7. 15.
백준 1238 / C++ https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net [ 풀이 ] 다익스트라+가벼운 발상을 필요로 하는 문제이다. 파티장에서 집으로 최단거리는 다익 1번으로 구해진다. 그런데 집에서 파티장까지 N개는 다익스트라 N번을 해야할까? 그렇게해도 시간안엔 풀리지만 다익 1번에 구할 수 있다. 역방향 그래프도 만든후에 파티장에서 다시 다익을 돌려주면 끝. [ 코드 ] #include using namespace std; type.. 2022. 7. 13.

티스토리툴바