6091. 핑크 플로이드(플래 V)
6091번: 핑크 플로이드
재현이는 N개의 정점으로 이루어진 트리를 가지고 있었다. 트리는 1~N까지의 번호가 정점에 매겨져 있었으며, 트리를 잇는 N-1개의 간선에는 두 정점을 잇는 거리가 저장되어 있었다. 재현이는 트
www.acmicpc.net
구해야 할 트리는 입력받은 그래프의 최소 스패닝 트리라는 것을 관찰하면 된다.
1994. 등차수열(플래 V)
1994번: 등차수열
N(1≤N≤2,000)개의 음 아닌 정수들이 있다. 이들 중 몇 개의 정수를 선택하여 나열하면 등차수열을 만들 수 있다. 예를 들어 4, 3, 1, 5, 7이 있을 때 1, 3, 5, 7을 선택하여 나열하면 등차수열이 된다.
www.acmicpc.net
공차를 a[i] - a[j]로 정해놓고 1 ~ j 에서 a[j] - a[m] = a[i] - a[j]인 m을 이분탐색으로 찾는다. 여기에 dp를 이용하자.
1086. 박성원(플래 V)
1086번: 박성원
첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다.
www.acmicpc.net
지금까지 쓴 값들과 그 때 각 나머지별 경우의 수를 저장해두면 쉬운 bit DP 문제가 된다.
12921. 제한된 메모리(플래 II)
12921번: 제한된 메모리
첫째 줄에는 4개의 정수 N, x0, a, b가 주어집니다. (1 ≤ N ≤ 2000000, 0 ≤ x0, a, b ≤ 1000000006) 둘째 줄에는 쿼리의 개수 Q이 주어집니다. (1 ≤ Q ≤ 1000) 셋째 줄에는 쿼리의 각 원소를 나타내는 Q개의
www.acmicpc.net
각 쿼리들을 저장해놓은 다음 병렬 이분탐색으로 한꺼번에 처리한다. 수열 X를 직접 구해주면서 인덱스와 mid값들을 비교하면 된다.
17081. RPG Extreme(플래 II)
17081번: RPG Extreme
요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서
www.acmicpc.net
문제에서 시키는 대로 열심히 구현하자!
18506. Find a Tree(다이아 III)
18506번: Find a Tree
Proper k-coloring of undirected graph G(V, E) is a mapping c : V → {1, 2, 3, . . . , k} such that for each edge (u, v) ∈ E, we have cu ≠ cv. Undirected graph is k-colorable if a proper k-coloring exists for it. Chromatic number of a graph is the sma
www.acmicpc.net
한 정점에서 출발해서 dfs 또는 bfs를 돌며 칠할 수 있는 색 중 가장 번호가 작은 색을 칠해준다. $i$번 색을 칠하기 위해서는 $1, 2, ... , i-1$번 색 정점과 연결되어 있고, $i$번 색과는 연결되어 있지 않아야 한다.
그러면 $K$번 색이 칠해진 정점에서 출발해서 다시 트리를 짠다. $K$번 색이 칠해진 정점은 1번부터 $K-1$번 색이 칠해진 정점과 모두 연결되어 있으므로, 트리의 모양이 어떻게 주어져도 원하는 트리를 만들 수 있다. (NO를 출력하는 경우가 없다!!)
2415. 직사각형(플래 I)
2415번: 직사각형
첫째 줄에 점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 점의 좌표 x y가 주어진다. 점의 좌표는 -10^8보다 크거나 같고, 10^8보다 작거나 같은 정수이다. 점의 좌표는 중복되지 않는다.
www.acmicpc.net
직사각형의 성질 중 대각선의 길이가 같고, 서로가 서로를 이등분해야 한다는 성질이 있다. 만들 수 있는 선 분 중 두 개를 골라 중점과 길이가 같다면, 직사각형이 된다. 구조체를 정의하고 정렬하면 스위핑으로 처리해줄 수 있다.
7981. 장비를 정지합니다(플래 IV)
7981번: 장비를 정지합니다
졸업논문을 완성하지 못한 형서는 학교에 대한 테러 계획을 세웠다. 고급정보과학 시간에 몰래 형서가 제작한 기계는, 전원을 켠 순간부터 폭주하기 시작해서 온 학교를 쑥대밭으로 만들고 있
www.acmicpc.net
간단한 그래프 dp 문제이다. 약한 충격을 주었을 때 필요한 전력을 (약한 충격을 주는데 필요한 전력) + (켜진 장비들에게 강한 충격을 주는 전력)으로 설정해놓고, 1번에서 출발해 dfs를 돌며 업데이트 해주면 된다.
14636. Money for Nothing(다이아 IV)
14636번: Money for Nothing
The first line of input contains two integers m and n (1 ≤ m, n ≤ 500 000) denoting the number of producer and consumer companies in the market, respectively. It is followed by m lines, the i th of which contains two integers pi and di (1 ≤ pi, di
www.acmicpc.net
dnc opt를 공부한 후 푼 가장 인상깊은 문제이다. 구하는 값은 $(q_i - p_j)(e_i - d_j)$의 최댓값인데, 최적이 될 수 없는 해 몇 개를 제외해주면 놀랍게도 Monge Array가 만들어진다. 좌표평면에 찍히는 점들이라고 생각하고 문제를 관찰해보자.
10526. 왜판원 순회(다이아 V)
10526번: 왜판원 순회
첫째 줄에 길이가 L이고 크기가 N인 싸이클이 존재한다면 "possible", 그렇지 않다면 "impossible"을 큰따옴표 없이 출력한다.
www.acmicpc.net
일일이 다 해보지 않고 중간에서 만나면 시간복잡도를 크게 줄일 수 있다.
18931. Graph Coloring(다이아 IV)
18913번: Graph Coloring
You are given a tournament, represented as a complete directed graph (for all pairs $i,j$ of two different vertices, there is exactly one edge among $i \to j$ and $j \to i$), with $n \leq 3000$ vertices. You need to color its edges into $14$ colors. There
www.acmicpc.net
각 정점에 비트가 7개이고 비트 14개로 이루어진 서로 다른 수들을 저장해놓으면 $i \rightarrow j$의 간선은 i에 저장된 수에는 없지만, j에 저장된 수에는 있는 비트가 나타내는 색이 된다.
'백준 문제 풀이' 카테고리의 다른 글
| 2021.06.02 problem solving (1) | 2021.06.02 |
|---|---|
| (BOJ 17372) 피보나치 수의 최대공약수의 합 (2) | 2021.01.09 |