본문 바로가기

분류 전체보기

 (74)
[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으로 만드는 것이 목표일 때 최소 연산 횟수를 구하는 문제다. 풀이 가능한 선에..
[BOJ 5846] Wifi Setup https://www.acmicpc.net/problem/5864 5864번: Wifi Setup Farmer John's N cows (1 N>>A>>B; for(int i=1;i>v[i]; v[i]*=2; } sort(v+1,v+1+N); for(int i=1;i

티스토리툴바