-
반응형
https://www.acmicpc.net/problem/12887
12887번: 경로 게임
첫째 줄에 바꿀 수 있는 하얀색 칸의 개수의 최댓값을 출력한다.
www.acmicpc.net
경로 게임
dp[i][state] 를 저장합니다.
state는
1행이 막혔을때 0..i까지 최대한 많이 막았을 때 최대값 (state=0)
2행이 막혔을때 0..i까지 최대한 많이 막았을 때 최대값 (state=1)
모두 막혔을 때 0..i까지 최대한 많이 막았을 때 최대값 (state=2) 을 저장합니다.
실제 지도애서 1행이 막혀있는 경우 state =1, state=2 는 -inf 를저장합니다.
state=0은 i-1에서 state=2, state=0 중 큰 dp값을 그대로 가져옵니다.
실제 지도에서 모두 열려있는 경우,
state=0은 i-1 state=2, state=0 중 큰 것에서 +1 을 합니다 (1행을 막으므로)
state=1도 비슷한 방식으로 구현합니다.
state=2는 i-1 state=0, 1, 2 중에 제일 큰 것을 구합니다.
i=n까지 모두 구한 후 리턴합니다.
https://www.acmicpc.net/problem/16971
16971번: 배열 B의 값
첫째 줄에 배열 A의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 배열의 원소가 주어진다. 배열은 정수로만 이루어져 있다.
www.acmicpc.net
B의 합은,
A[i][j] * 4 ( i, j가 끝이 아닌 경우)
+ A[i][j] * 2 ( i, j가 모서리인 경우)
+ A[i][j] (i, j가 꼭지점인 경우) 입니다.
B의 합이 최대가 되려면,
해당하는 열을 모서리쪽으로 올라갔을 때,
변경되는 값이 최대가 되어야 합니다.
그러기위해서 각 열의 A[i][j] 의 합을
모서리에 있을 경우와 중앙에 있을 경우로
나누어서 계산한 다음,
그 차이가 가장 클 경우에만 계산하여 리턴합니다.
https://www.acmicpc.net/problem/8364
8364번: Idempotent Functions
You are given a positive integer n. By A we mean the set {1, 2, 3, ..., n}. Function f : A → A is called a permutation if it is injective (for distinct arguments returns distinct values). Function f : A → A is called idempotent if for every
www.acmicpc.net
예제를 살펴봅니다.1이 2개,
4가 3개,
1이 2개,
7이 2개입니다.
h는 idempotent 해야 하는데,f(a)=h(g(a)) = 1 이라면
h(h(g(a)) = h(1) 이므로
g(a)= 1이어야 합니다.
즉 1 2개 중 1개는 고정이고
4 3개중 2개는 고정입니다.
그러므로 나머지 원소들 중에서 자유롭게 배치를 하면 됩니다.
한편 이 자유롭게 배치하는 것은 g의 조건때문에 팩토리얼로 구할 수 있습니다.
따라서 4!/2!/1!/1! * 4! = 288입니다.
즉 각 원소가 몇번 등장하는지 세고,
중복-1 개씩 비례배분한 뒤에 나누어서 구하고,
분모는 중복-1의 합들을 팩토리얼을 한 뒤에 제곱을 구하면 됩니다.
mod가 큰 소수므로, 팩토리얼을 나눌 때는 페르마의 소정리로 모듈러 역원을 구해서 계산합니다.
https://www.acmicpc.net/problem/17150
17150번: Azulejos
The first line of input contains an integer n (1 ≤ n ≤ 5 · 105), the number of tiles in each row. The next four lines contain n integers each; the first pair of lines represents the back row of tiles and the second pair of lines represents the front r
www.acmicpc.net
뒷열과, 앞열을 먼저 가격순으로 정렬합니다.
같은 가격 그룹안에서,
높이를 어떻게 배치할지가 문제입니다.
같은 그룹에서 뒷열의 개수가 앞열의 개수보다 많다고 해 봅시다.
그러면 뒷열 중에서 제일 높이가 작은 것을 골라냅니다.
그리고 앞열 중에서 뒷열의 그 상품 보다 높이가 작되 그 중에서 가장 큰 것을 구합니다.
이는 set등의 자료구조에서 Upper_bound 를 사용하면 됩니다.
앞열의 개수가 뒷열의 개수보다 많다고 해 봅시다.
그러면 앞열 중에서 제일 높이가 큰 것을 고릅니다.
그리고 뒷열 중에서 앞열의 그 상품보다 높이가 크되 그 중에서 제일 작은 것을 구합니다.
이를 반복적으로 구하면 시간복잡도 내에 답을 구할 수 있습니다.
https://www.acmicpc.net/problem/17153
17153번: Circular DNA
You have an internship with a bioinformatics research group studying DNA. A single strand of DNA consists of many genes, which fall into different categories called gene types. Gene types are delimited by specific nucleotide sequences known as gene markers
www.acmicpc.net
어떤 DNA가 nested 구조를 이루려면,
si의 개수와 ei의 개수가 정확히 같아야 합니다.
si가 나올 때 +, ei가 나올 때 -을 하는 누적합 배열을 생각해 봅시다.
계산을 잘해보면 이 누적합 배열에서 값이 최소가 되는 부분에서 끊으면,
nested 구조를 이루는 것을 볼 수가 있습니다.
각 si에 대해서 이런식으로 최소가 되는 구간들을 반복적으로 저장한 뒤에,
그 구간들을 정렬합니다.
0부터 n까지 구간을 훑으면서, 구간이 가장 많이 겹치는 부분에서 끊으면 그곳이 최적입니다.
https://www.acmicpc.net/problem/17154
17154번: Dead-End Detector
On the first line, output k, the number of dead-end signs installed. On each of the next k lines, output two integers v and w marking that a dead-end sign should be installed at the v-entrance of a street connecting locations v and w. The lines describing
www.acmicpc.net
풀지 못해서 이후살펴볼 예정입니다.
https://www.acmicpc.net/problem/16183
16183번: Electronic Circuit
The first line contains two integers, $n$ and $m$ ($2\leq n\leq 100,000$, $1\leq m\leq 300,000$), where $n$ is the number of nodes and $m$ is the number of wires. All nodes are numbered from $1$ to $n$. In the following $m$ lines, each line contains two in
www.acmicpc.net
풀지 못해서 이후 살펴볼 예정입니다.
반응형'백준' 카테고리의 다른 글
백준 문제 풀이 (0) 2022.07.05 엣코더 ARC 142 풀이 (0) 2022.06.28 2021 KAKAO BLIND RECRUITMENT 1차 코딩 테스트 모든 문제 코드 및 해설 (0) 2021.02.09 삼성 SDS 대학생 동계 알고리즘 특강 후기 (2) 2021.02.08 카카오 블라인드 코딩 테스트 2021 1차 솔루션 (2) 2020.09.12