본문 바로가기

boj

BOJ 1019 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 문제를 풀기 위해 재귀 호출을 하면서, 문제의 구조를 일관되게 유지하는 게 핵심이다. 7683을 생각해보자. f(7683, 1) 은 1~7683까지 일의 자리에 각 숫자가 등장하는 횟수를 세야 한다고 하자. 1~7683까지 일의 자리에 각 숫자가 몇 번씩 등장하는지 카운팅은 금방 할 수 있다. 문제는 십의 자리에서 등장 횟수를 구하기 위해 다음 재귀 호출을 할 때, 문제의 구조를 유지하기가 어렵다. 재귀 호출 구조를 간단하게 만들어야 한다. 재귀 호출 안에서.. 더보기
BOJ 10775 공항 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 숫자가 1부터 G까지 하나씩 있는 집합 A가 있을 때 주어진 숫자 x에 대해 아래의 연산을 수행한다. 집합 A에서 x보다 작거나 같은 원소 중 가장 큰 숫자를 찾는다. 위에서 찾은 원소를 A에서 제거한다. 위에서 찾은 원소를 반환한다. 일감은 구간 트리(segment tree)를 이용하여 해결하는 것이다. 구간 트리에 대해서 i번째 원소를 i로 초기화 한다. x에.. 더보기
BOJ 12858 Range GCD https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net gcd(a, b, c, d, e) = gcd(a, |b - a|, |c - b|, |d- c|, |e - d|) 임을 이용해야 한다. (이 부분이 핵심이다) 어떤 구간에 속한 모든 원소에 x를 더한 더하는 경우, 그 구간 내에서 이웃한 원소들 사이의 차이는 변화가 없다. 그 구간의 경계에 인접한 원소와의 차이에만 변화가 발생한다. GCD를 계산하기 위한 세그먼트 트리에는 인.. 더보기
BOJ 1031 스타대결 https://www.acmicpc.net/problem/1031 1031번: 스타 대결 첫째 줄에 지민이의 팀의 팀원 수 N과 한수의 팀의 팀원 수 M이 주어진다. 둘째 줄에는 지민이의 팀의 각 팀원이 해야 하는 경기의 수가 주어지고, 셋째 줄에는 한수의 팀의 각 팀원이 해야 하 www.acmicpc.net 우선 규칙 1~3을 만족하는 대진을 만드는 것은 최대 유량(max flow)을 이용하여 푸는 해법을 생각할 수 있다. 지민이의 팀을 왼쪽에, 한수의 팀을 오른쪽에 이분매칭 하듯이 배열한다. 지민이 팀 집합을 L, 한수팀 집합을 R이라고 하자. 양 팀 간 모든 쌍에 대해, 다시 말해 모든 L의 정점에서 R의 모든 정점으로 capacity 1의 간선을 추가한다. 최대 유량 그래프의 소스 정점에서 L의 .. 더보기
BOJ 24231 해석 https://www.acmicpc.net/problem/24231 24231번: 해석 $($와 $)$로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 중, 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다. 빈 문자열은 올바른 괄호 문자열이다. $A$가 올바른 괄 www.acmicpc.net 컨디션 난조로 3주만에 처음으로 문제를 풀어봤다. 어떠한 암호 문자열이 주어졌을 때, 이 암호 문자열을 분해하는 방법은 아래의 두 가지 방법이 있다 AB - A와 B모두 올바른 암호 문자열. 대응 가능한 괄호 문자열 -> (...)(...) xAy - A는 올바른 암호 문자열, x와 y는 서로 다른 암호 문자. 대응 가능한 괄호 문자열 ((..)) 주어진 문자열을 부분 문자열로 분해하여 각각 문.. 더보기
BOJ 11717 Wall Making Game (Game Theory) https://www.acmicpc.net/problem/11717 11717번: Wall Making Game The first line of the input consists of two integers H and W (1 ≤ H, W ≤ 20), where H and W are the height and the width of the board respectively. The following H lines represent the initial board. Each of the H lines consists of W characters. The j-t www.acmicpc.net 전형적인 impartial game으로 스프라그-그런디 정리(Sprague-Grundy Theorm)를 이용하는 것이 .. 더보기
BOJ 10531 Golf Bot (FFT) https://www.acmicpc.net/problem/10531 10531번: Golf Bot Do you like golf? I hate it. I hate golf so much that I decided to build the ultimate golf robot, a robot that will never miss a shot. I simply place it over the ball, choose the right direction and distance and, flawlessly, it will strike the ball across www.acmicpc.net 200000 이하의 숫자로 이루어진 집합이 주어진다. 이어서 어떤 수들이 주어졌을 때, 앞서 주어진 집합의 원소 하나 혹은 두 .. 더보기
BOJ 6171 땅따먹기 (볼록껍질 최적화) https://www.acmicpc.net/problem/6171 6171번: 땅따먹기 (1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다. www.acmicpc.net 볼록껍질 최적화가 일감 이었으나 쉽게 점화식을 유도하지는 못했다. 우선 두 개의 땅 a, b에 대해서 W_a >= W_b 이고 H_a >= H_b 이면, 땅 b는 땅 a와 한 묶음으로 사는게 무조건 이득이다(추가 비용이 발생하지 않는다). 전처리를 해서 b와 같은 땅을 모두 걸러낸 뒤, 너비에 대해서 오름차순으로 정렬을 하면 높이는 내림차순으로 정렬이 된다. 너비에 대해 정렬이된 세 개의 땅 a, b, c를 생각해보자. 이때 (a, c.. 더보기
BOJ 17429 국제 메시 기구 https://www.acmicpc.net/problem/17429 17429번: 국제 메시 기구 첫째 줄에 N, Q가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 100,000) 다음 N-1줄 중 i번째 줄에는 Si, Ei가 주어지며, 이는 금고 Si와 금고 Ei가 연결되어 있다는 뜻이다. (1 ≤ Si, Ei ≤ N) 금고가 연결된 모 www.acmicpc.net 1감은 HLD를 이용한 풀이인데, 서브 트리 쿼리 처리를 어떻게 하는지에서 생각하느라 고생을 많이 했다. 우선 서브 트리 쿼리는 오일로 경로 테크닉을 이용해서 트리를 일자로 늘어뜨리면 해결이 된다. 트리를 순회(preorder traverse)하면서 노드의 발견 시각과 종료시각을 기록한다. 노드의 발견시각을 그 노드의 인덱스로 .. 더보기
BOJ 16074 Mountaineers (병렬 이분 탐색) https://www.acmicpc.net/problem/16074 16074번: Mountaineers The Chilean Andes have become increasingly popular as a destination for backpacking and hiking. Many parts of the Andes are quite remote and thus dangerous. Because of this, the Ministry of Tourism wants to help travelers plan their trips. In particular, t www.acmicpc.net 지형이 주어지고, 어느 두 지점을 이동하는 경로 중 경로상 최고 고도를 최소화하는 문제이다. 쿼리의 개수가 5만개 이므.. 더보기

티스토리툴바