본문 바로가기

BOJ

 (56)
[BOJ 18313] Cave Paintings https://www.acmicpc.net/problem/18313 18313번: Cave Paintings Bessie has become an artist and is creating paintings of caves! Her current work in progress is a grid of height $N$ such that each row of the grid contains exactly $M$ squares ($1\le N,M\le 1000$). Each square is either empty, filled with rock, or filled www.acmicpc.net Tag : DSU, Tree DP 문제요약 이차원 격자에서 서로 다른 칸 a,b가 min(a의 높이, b의 높이)인 ..
[BOJ 13261] 탈옥 https://www.acmicpc.net/problem/13261 13261번: 탈옥 한 간수가 1, 2, 3번 방을, 다른 간수가 4, 5번 방을, 다른 간수가 6번 방을 감시한다고 하면 탈옥 위험도가 최소가 된다. 1, 2, 3번 방을 감시하는 간수는 총 3명의 죄수를 감시하고 있기 때문에, 1, 2, www.acmicpc.net Tag : dnc opt 문제요약 간수 한명이 구간 \([l,r]\)을 관리할 때 이 위험도는 구간의 탈옥력 \(C_i\)들의 합과 구간의 크기인 \(r-l+1\)의 곱으로 정의된다. 간수가 G명일 때 \([1,L]\)의 위험도의 합을 최소화하는 것이 목표다. 풀이 직관적으로 떠올릴 수 있는 dp의 정의는 다음과 같다. \(dp_{i,j}:=i\)명의 간수가 \([1:j]..
[BOJ 11001] 김치 https://www.acmicpc.net/problem/11001 11001번: 김치 첫 번째 줄에 날짜의 수와 시간 제한 N, D가 주어진다. (1 ≤ D ≤ N ≤ 100,000) 두 번째 줄에 온도 Ti가 주어진다. N-1 이하의 정수 i에 대해서 Ti >= Ti+1을 만족하며, 109 이하의 자연수이다. 세 번째 줄에 www.acmicpc.net Tag : dnc opt 문제요약 (숙성시간)*(꺼낼 때의 온도)+(넣은 날의 가치)의 최대를 구하는 문제다. \(D_i:=i\)일에 넣었을 때 최대"라 정의하고 문제가 요구하는 대로 식을 세우면 \(D_i=max_{iP(i+1)\)에 모순된다. 따라서 \(P(i)\leq P(i+1)\)이다. (그냥 monge array인거 보이는게 낫다) + 맞은사람..
[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번 ..

티스토리툴바