Bibidi

12713번: Ugly Numbers (Small) Once upon a time in a strange situation, people called a number ugly if it was divisible by any of the one-digit primes (2, 3, 5 or 7). Thus, 14 is ugly, but 13 is fine. 39 is ugly, but 121 is not. Note that 0 is ugly. Also note that negative numbers can www.acmicpc.net 구현만 해도 실5 난이도는 아닌 거 같고 숫자 길이 함정도 있어서 초보들 죽이기 딱 좋은 문제. 되는 경우 다 만들고 만들어진 수가 2, 3, 5, 7로 나누어지는지 확인하면 ..

2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 첫 번째 시험을 기준으로 오름차순으로 정렬한다. 그러면 어떤 학생을 기준으로 그 앞에 있는 학생은 모두 첫 번째 시험에서 그 학생보다 좋은 성적을 받은 학생이다. 여기서 두 번째, 세 번째 시험도 더 잘 친 사람이 있는지 체크하면 된다. 두 번째 시험을 나보다 잘 친 사람이 없다면 정답이 하나 증가하고 그렇지 않은 경우 두 번째 시험을 나보다 잘 친 사람들 중에서 나보다 세 번째 시험을 잘 친 사람이 있는지 확인하면 된다. 세그먼트 트리의 리프 노드 i를 두 번째 시험 ..

9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 라이 갓갓님 덕분에 좋은 문제도 많이 풀고 아이디어도 많이 얻는다. 트리의 리프 노드에 각 DVD의 위치를 저장하고, 업데이트 할 때 그 범위의 DVD 위치들 중 최솟값, 최댓값이 뭔지 파악하면 된다. 0 ~ 4 범위를 검사할 때 최솟값이 0이고 최댓값이 4이면 어떻게든 그 범위 안에 DVD 0, 1, 2, 3, 4가 다 있다는 의미이다. - Source code link github.com/Bibidi/Algorit..

1280번: 나무 심기 첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다. www.acmicpc.net 현재 심는 나무 위치 기준으로 왼쪽, 오른쪽 나눠서 생각한다. 왼쪽에 있는 모든 나무와 현재 새로 심을 나무의 거리 차이의 합은 왼쪽에 있는 나무의 개수 * (현재 위치) - 왼쪽 나무의 거리합이고 오른쪽에 있는 모든 나무와 현재 새로 심을 나무의 거리 차이의 합은 오른쪽에 있는 나무의 거리합 - (현재 위치) * 오른쪽에 있는 나무의 개수이다. 주의점은 같은 곳에 나무를 여러 번 심을 수 있다는 점. 오버플로우를 주의해야 한다는 점. % 연산과 * 연산의 순..

3006번: 터보소트 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다 www.acmicpc.net 풀이 각 숫자가 어느 자리에 있는지 먼저 기록한다. 숫자 i를 정렬할 때 맨 앞이나 맨 뒤로 보내 정렬하므로 숫자 i가 있는 위치와 가야되는 위치 사이에 있는 숫자의 개수를 파악하면 된다. 그리고 정렬된 숫자를 제외하고 같은 작업을 반복하면 된다. 1을 맨 앞, n을 맨 뒤로 추상화할 수 있다. #include using namespace std; typedef long long ll; int tree[1 > n; for (base = 1; base ..

2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 세그먼트 트리 응용 문제. 사탕맛이 a인 사탕이 몇 개인지 tree[base + a]에 업데이트하고 k 번째 사탕을 찾아서 내주면 된다. k 번째 사탕은 사탕 맛의 크기가 작은 쪽에서 k 번째이다. 루트에서 왼쪽으로 내려가서 찾을지 오른쪽에서 내려가서 찾을지 정해야 하는데, 왼쪽에 사탕이 k 개 이상 있을 땐 왼쪽으로 가고 그렇지 않을 땐 오른쪽으로 가서 k - 왼쪽 사탕의 개수 번째 사탕을 찾으면 된다. - Source code link..

10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 빈 방에 비행기를 채워 넣는 문제입니다. 숫자가 작은 방일수록 더 많은 종류의 비행기를 넣을 수 있으므로 g_i보다 같거나 작은 빈 방 중 가장 큰 빈 방부터 써야 합니다. 이걸 어떻게 구현할 수 있을까요 ? 처음 set에 빈 방을 모두 넣어줍니다. 이때 set이 내림차순이 되도록 설정하면 set.lower_bound(t)를 이용하여 t와 같거나 작은 방을 logN에 찾을 수 있습니다. g_i보다 같거나 작은 방 중 가장 큰 방을..

14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net 백조의 호수랑 비슷한 문제. 옛날에 백조의 호수 풀 땐 유니온 파인드를 몰라서 서로 이어졌는지 확인하는 과정을 까다롭게 구현했었는데, 유니온 파인드를 알고 나니 체감 난이도가 확 떨어짐. 서로 다른 문명을 합치는 과정과 문명이 없는 곳에 문명을 전파하는 과정을 따로 구현하면 된다. 먼저 문명을 합치는 큐를 돌리고 그 과정에 사용된 큐를 다시 전파용 큐로 전달해주고 문명 전파 후 새로 추가된 큐를 문명을 합치기 용 큐로 보내는 과정을 반복하..