본문 바로가기

전체 글

 (74)
[BOJ 15462] The Bovine Shuffle https://www.acmicpc.net/problem/15462 15462번: The Bovine Shuffle Convinced that happy cows generate more milk, Farmer John has installed a giant disco ball in his barn and plans to teach his cows to dance! Looking up popular cow dances, Farmer John decides to teach his cows the "Bovine Shuffle". The Bovine Shuffle consi www.acmicpc.net Tag : permutation graph 문제요약 permutaion graph를 몇번을 전이시키던 항상 ..
[BOJ 15770] QueryreuQ https://www.acmicpc.net/problem/15770 15770번: QueryreuQ 어떠한 문자열에 대해서, 이 문자열을 뒤집어도 같은 문자열이 나온다 이 문자열을 팰린드롬이라 부른다. 예를 들어, "a", "aa", "appa", "queryreuq"와 같은 문자열은 모두 팰린드롬이다. 당신은 빈 문 www.acmicpc.net Tag : dynamic programming 문제요약 이 두가지 연산을 Q개 처리하면서 매 연산마다 현재 S의 부분 문자열 중 팰린드롬의 개수를 출력하라. 풀이 \(dp_{l,r}=[s[l,r]\)는 팰린드롬\(]\)이라 정의하고 매 쿼리마다 \(1\leq i \leq S.size\)인 i에 대해 \(dp_{i,S.size}\)를 모두 갱신해주면 된다. Q=1..
[BOJ 11973] Angry Cows (Silver) https://www.acmicpc.net/problem/11973 11973번: Angry Cows (Silver) The first line of input contains \(N\) (\(1 \leq N \leq 50,000\)) and \(K\) (\(1 \leq K \leq 10\)). The remaining \(N\) lines all contain integers \(x_1 \ldots x_N\) (each in the range \(0 \ldots 1,000,000,000\)). www.acmicpc.net Tag : Binary search 문제요약 K개의 폭발을 일으켜 모든 건초더미를 없애야하는데 수직선 상의 좌표 x에 폭발을 일으키면 구간 \([x-R,x+r]\)의 건초더미를 없앨 ..
[BOJ 8980] 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net Tag : Greedy 문제요약 (보내는 마을 번호, 도착하는 마을 번호, 보내는 상자의 수)를 의미하는 (s,e,v) 쌍 M개와 트럭의 최대 용량 C가 주어질 때 배송할 수 있는 최대 박스 수를 구하는 문제다. 풀이 (s,e,v)를 (s,e,1) v개로 쪼개보자. 그러면 회의실이 C개인 회의실 배정 문제로 환원된다. * 회의실 배정 문제는 (s,e)에서 e가 작은걸 우선으로 ..
[BOJ 20188] 등산 마니아 https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net Tag : Tree dp, complement set 두가지 풀이로 풀어봤는데 둘 모두 꽤 교육적인 풀이였다. sol1) Tree dp \(sz_i:=\)i를 루트로 가지는 서브트리의 사이즈 \(sum_i:=\)i를 루트로 가지는 서브트리의 모든 원소에서 i로 향하는 경로의 합 이 두 정보를 가지고 있다면 dfs(x)에서 x를 lca로 가지는 두 정점에 대한 처리를 모두 할 수 있다. 1번 ..
[BOJ 5551] 쇼핑몰 https://www.acmicpc.net/problem/5551 5551번: 쇼핑몰 첫째 줄에 도시의 수 N, 도로의 수 M, 쇼핑몰이 있는 도시의 수 K가 주어진다. 도시는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 3000, 1 ≤ M ≤ 105, 1 ≤ K ≤ N) 다음 M개 줄에는 도로의 정보 a, b, www.acmicpc.net Tag : dijkstra 문제 요약 정점마다 가장 가까운 쇼핑몰과의 거리를 \(A_i\)라 정의할 때 이 \(A_i\)의 최대를 구하는 문제다. 풀이 최단경로...->최소.....최대........ 파라메트릭?하면서 뇌절할뻔했다. 가장 멀리 있는 집은 어떠한 간선의 양 끝 또는 간선 위에 존재한다. 그래서 모든 간선을 확인하면서 \(\lceil (dis..
[BOJ 15732] 도토리 숨기기 https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net Tag : binary search 문제 요약 "\([l,r]\)에서 x간격으로 도토리를 하나씩 배치한다." 라는 규칙이 \(K\)개 존재한다. 이 때 \(D\)번째 도토리가 위치한 상자를 찾는 문제다. 풀이 1~i까지 상자의 도토리 개수 합이 단조증가하기 때문에 이분탐색을 사용할 수 있다. 1~i까지의 도토리 ..
[BOJ 5837] Poker Hands https://www.acmicpc.net/problem/5837 5837번: Poker Hands Output Details Bessie can play a straight from 1 to 5, a straight from 1 to 2, a straight from 4 to 5, two straights from 2 to 2, and a straight from 5 to 5, for a total of 6 rounds necessary to get rid of all her cards. www.acmicpc.net Tag : Greedy 문제요약 구간 [l,r]의 모든 원소를 1씩 줄일 수 있는 연산이 있고 모든 원소를 0으로 만드는 것이 목표일 때 최소 연산 횟수를 구하는 문제다. 풀이 가능한 선에..

티스토리툴바