안녕하세요, 글 쓰는걸 계속 미루다보니 벌써 이렇게 긴 시간이 흘렀군요
완전 놀진 않았고.. 문제는 나름 계속 풀었습니다. 대회 검수, 출제도 했고.. 그래도 구정에는 검수한거 하나씩 내면서 스트릭만 이었던것 같네요.
암튼 제가 잘 기억할지는 모르겠지만 그동안 푼 문제를 난이도 상관없이 다 적어봅시다. 문제가 좀 많을거라 코드는 따로 안올릴것같네요. 코포 문제들도 있을텐데 카테고리는 그냥 백준으로 두는게 맞는가..? 이거에 대한 고민은 나중에 해보죠
일단 백준 문제를 쭉 쓰다가 코포 문제를 쭉 쓸거같은데 어떻게 될지 모르겠습니다. 생각나는 순서로 쓸지도?
각각 $N$명의 사람이 있는 팀 $A$와 팀 $B$가 토너먼트 경기를 합니다. 모든 경기는 $1$대$1$로 이루어지고, 팀 $A$의 모든 사람과 팀 $B$의 모든 사람은 경기를 해서 $N^{2}$개의 경기를 치뤘습니다. 하지만 정규 경기가 아닌 연습 경기를 같은 팀원끼리 혹은 다른 팀원끼리 추가적으로 진행했을 수 있습니다.
경기를 치룬 쌍이 $M$개 주어질 때 가능한 팀 $A$의 구성 개수를 구하고, 그 중 하나를 출력하세요
다른 팀이면 무조건 경기를 치뤘다는 것은, 경기를 치루지 않은 두 사람은 무조건 같은 팀이어야 한다는 것입니다. 따라서 서로 경기를 하지 않은 사람들끼리의 간선을 만들어주고, 플러드필 등을 통해 그룹화를 해준 뒤 크기 $N$을 채우는 배낭 문제를 해결하여 팀 $A$의 구성 개수를 계산할 수 있습니다. 구현을 좀 많이 절었던 것 같군요. 유니온 파인드로도 풀리나? 몰?루
반지름이 $1, 2, \cdots, N$인 팬케이크를 원하는 순서대로 구워서 쌓습니다. 그러면 $i$번째 팬케이크까지 구웠을 때 위에서 내려다보면 반지름이 작은 애들은 묻힐거고, 큰 애들은 보일거고.. 대충 몇 개의 팬케이크가 보이는지 생각해볼 수 있습니다. 문제는 $i$번째에 $A_i$개의 팬케이크가 보였다고 할 때 그것이 가능하도록 하는 팬케이크 굽기 순서의 경우의 수를 구하는 문제입니다.
먼저 할 수 있는 관찰은 $A_i > A_{i-1}+1$이라면 불가능 하다는 겁니다. 자명한듯?
이걸 제외하고 이제 개수를 세면 되는데, 특정 구간을 채울 때 해당 구간에서 $A_i$가 가장 작고, 그 중에서 인덱스가 가장 큰 놈을 기준으로 양 구간을 분할할 수 있습니다.
이게 왜 되냐면..흠 왜 되더라? 일단 초기 상태 $N$개 다 차있는 상태에서 $A_i = 1$이고 인덱스가 가장 큰 위치에는 무조건 반지름이 $N$인 팬케이크가 들어가야 합니다. 그리고 가장 큰걸 덮었으니 앞에 있는 $1~i-1$까지의 인덱스는 전부 무시해도 되겠죠. 그럼 자명한거같군요
암튼 그래서 구간 크기가 $N$인 곳에 $K$번째 위치에 가장 큰거 놓는다고 치고, 양쪽은 아무렇게나 해도 되니까 $\binom {N-1} {K-1}$이 곱해지겠죠. 이걸 재귀적으로 풀면 됩니다.
뭔가 구간 최소는 카르테시안 트린가 뭐시긴가로 되나 모르겠는데 전 그런거 몰라서 걍 세그로 밀었습니다.
구간 $[a, b]$, $[c, d]$가 주어지면 $a \le x \le b$와 $c \le y \le d$를 만족하는 $x$, $y$에 대하여 서로소인 $(x, y)$쌍을 구하는 문제.
뫼비우스 딸깍.. 별로 할 말은 없다
[BOJ 17717] En-JOI-able Logo Design
원형으로 쓰여진 문자열에서, 어떤 시작 위치를 기준으로 J, O, I가 각각 순서대로 $4^k$개가 연속해서 등장하도록 바꿔야 하는 최소 문자열 개수 구하기.
누적합을 해주고 브루트포스를 잘 해주면 된다.
[BOJ 26867] Easily Distinguishable Triangles
격자의 각 칸이 ?, ., #중 하나로 채워져 있다. .은 흰색 사각형, #은 검은색 사각형, ?는 이제 내가 채워야 하는 칸.
채워야 하는 칸은 인접한 두 변이 검은색인 직각삼각형으로 채워야 한다. 이제 검은색 변이 맞닿지 않도록 채우는 경우의 수를 구해보자. 나름 재밌는 문제인듯?
나름 많이 쓰는 아이디어인것 같은데, 직각삼각형으로 채운다는 것은 상하와 좌우끼리 독립적이다. 따라서 이를 행과 열을 독립적으로 처리하면 된다.
한 줄은 어떻게 처리하냐면, 채워야 하는 칸이 연속된 $k$개의 칸이라고 하자. 연속된 $k$개의 칸의 양 끝이 검은색이라면 불가능, 한쪽만 검은색이라면 $1$가지, 양쪽 모두 흰색이라면 $k+1$가지의 채우는 방법이 있다. 이걸 각각 계산해서 독립이니 전부 곱해주면 답이다.
문제 지문이 깔끔하지가 않아서, 제대로 기억하는지 모르겠는데 대충 리프노드들에 대해 길이 $M$의 염기 서열이 주어진다. 이때 ATGC중 하나로 정해져서 주거나, ?로 주는데 ?는 내가 마음대로 선택할 수 있다.
이제 부모에서 자식으로 갈 때 염기 서열의 변화에 따라 비용이 발생하는데, 리프 노드만 염기 서열을 줬으니까 부모 노드들도 염기 서열이 존재할거고, 내가 그것들을 적절하게 선택해서 총 비용을 최소화 하면 되는 문제였던것 같다.
대충 풀이는 바로 보인다. 염기 서열의 각 위치는 독립적이고, 따라서 $i$번 염기 서열에 대한 답을 독립적으로 해결해주면 된다. 이거는 이제 tree dp를 짜면 되는데, 다음 노드의 값이 $x$일 때 값을 가져와서 최솟값 갱신해주면 됐던듯. 리프 노드에 도달했을 때에는 값이 $x$인지 $?$인지 나머지인지에 따라 $0$ 혹은 INF로 갱신해주면 된다. 열심히 구현하자.
팀연습도 한번 했다. 같이 돈 사람은 solved.ac기준 akim9905와 js9028.
시간이 꽤 지나서 구체적인 타임라인같은건 쓰기 힘들 것 같고.. 이때 아마 새벽 2시부터 7시까지 팀연습을 했는데 장난치고 놀면서 한것치곤 나름 나쁘지 않게 한것같다.
(~0:13) 제가 I를 풀었습니다. 처음에 문제를 잘못읽었는데.. 아무튼 Fizz와 Buzz가 나오면 적절히 $a$와 $b$를 매핑해주고, 나오지 않았다면 $d+1$로 매핑해주면 됩니다.
(~0:34) js9028이 C를 풀었습니다. 반지름이 $x$인 원점을 중심으로 하는 원 내부에 완전한 격자가 $s$개 이상 들어오는 최소 $x$를 구하는 문제이고, 실수 이분탐색을 쓰면 됩니다. 쉬운 문제인데 뭔가 이상한 실수로 5번이나 틀리셨군요. 이게 이분의 장점이자 단점인데.. 개선해서 팀 대회에서 좋은 성적을 받아왔으면 좋겠습니다. 참고로 전 아마 이분들과 팀대회를 나가기는 어렵습니다. 군이슈때문에..
(~1:10) akim9905가 D를 풀었습니다. 제가 옆에서 그림만 보고 뭐하는 문제인지 맞췄습니다. 대충 격자가 원 또는 사각형으로 채워져 있을때 최단경로 구하기? 잘 짜면 풀린다고 합니다.
(~1:25) 제가 긴 삽질 끝에 B를 풀었습니다. 왜 PS에 물리학 문제가 나오는것인지.. 무게중심을 구하려면 거리 곱해야하는거 생각안나서 시간을 오래 버렸네요 그래도 예제가 안나와서 이상한 풀이를 제출을 못해가지고 패널티는 없습니다..
(~1:37) js9028이 E를 풀었습니다. 이거에 대해 하고싶은말이 많지만.. 아니 저한테 풀어달라고 해서 열심히 풀고 코드짜고있는데 자기가 짜서 내서 맞았대요 시간낭비 뭐임;; 암튼 풀이는 둘이 같더라고요
문제는 재밌습니다. 마음대로 그래프 구성해서 정점$1$까지의 최단거리의 기댓값이 $a/b$인 그래프 구성하기. 저희가 낸 풀이는 $1$에다가 직선으로 최대한 잇다가 $1$에 왕창 붙여주고 직선 길이가 $k$라면 $1~k$사이 적절히 붙일 수 있으니까 그렇게 짜면 됩니다. 별개로 입력이 $a/b$인데, scanf로는 %d/%d로 날먹이 되는데 string으로 받아서 파싱하고 계시더군요. 다들 킹갓 scanf씁시다.
(~2:20) js9028이 H를 풀었습니다. 제곱처럼 보이는 tree dp를 필요한 상태만 저장해서 들고가면 시간내에 돈다네요. pba한듯
(~2:36) akim9905가 J를 풀었습니다. 처음에 js9028과 제가 이상한 헛소리를 했는데, 결국 문제는 그냥 2차원 lis를 구하는 문제였습니다. 휘리릭 짜면 풀림
(~3:58) 다같이 G를 풀었습니다. 코딩은 js9028이 했습니다. 정말 재밌는 문제이니 꼭 풀어보세요. 물론 저는 입풀이만 냈고 구현해보고 싶진 않은데.. 언젠간 짜보죠
(~5:00) 뭘 잡을까 하다가 다같이 K를 봤고, 여러 핵심 관찰을 한거같은데 시간이 모자라서 못풀었습니다. 덜 놀고 진지하게 쳤으면 풀었을듯. 나중에 에디토리얼 보니 풀이가 같더라고요
이렇게 셋이 하면 나름 조합이 나쁘진 않은데, 절대 이루어질 수 없는 팀이라는게 아쉬운 점이죠. 화이팅 하시기 바랍니다.
[BOJ 7997] Sequences without Stammers
같은 문자열이 연속해서 나타나지 않는 길이 $N$의 사전순 최소 문자열 출력하기.
제한이 너무 커서, 그리고 걍 직관적으로 $a$, $b$, $c$ $3$개만 써도 풀릴 것처럼 생겼습니다. 문제 자체는 나름 유명한 문제인 것 같습니다. Square-free word라고 하는듯?
구성은.. $i$번째 칸을 채울때 $i$를 2진법으로 나타냈을 때 켜진 비트 수의 기우성에 따라 $a$혹은 $b$를 채우고, 이게 조건에 위배될 때 적절히 $c$를 잘 채우면 되는듯하네요. 정확히는 기억이 잘..
문제에 써져 있는 식의 값을 구하래요.
이게 왜 티어가 이렇게 높지.. 대충 2차원 배열 그려보고 값 몇개 채워보면 답이 나와서 짜면 풀립니다.
$s$와 $k$가 절반씩 무작위 순서로 섞여있는 문자열을 받았을 때, 최소 횟수로 잘라서 $s$와 $k$를 각각 또 절반씩 분배하는 문제.
걍 딱보면 답은 $1$또는 $2$일것처럼 생겼습니다. $1$이 되는지 보는건 쉽고 $2$가 되는지는 슬라이딩 윈도우를 슥슥 짜면 되겠죠. 굿
대충 $N$이 주어지면, $N$을 $a_1 \times a_2 \times \cdots \times a_k$로 나타낼 수 있을거고, 이때 $(a_1-1)+(a_2-1)+ \cdots + (a_k-1)$의 값으로 가능한 값을 모두 구하는 문제.
뭔가 되게 이상하게 푼거같은데 흠 이게 정해가 맞나.. $N$의 약수를 모두 구하고 모든 약수 쌍에 대해서 서로 나누어 떨어지면 그때로 가능한 결과값을 잘 채워나간거 같네요. 약수 개수가 대충 $N^{1/3}$일테니 뭐 잘 돌만한 풀이이긴 한가? 모르겠습니다.
정수 $0$에 $-x$혹은 $ \sim x$를 $N$번 할 수 있을 때 $M$을 만드는 경우의 수 구하기. 재밌는 문제다
$- \sim x$와 $ \sim - x$를 하면 어떻게 되는지 보자.
연산자 위치를 잘 조정해서 이항계수 테이블처럼 전이가 되도록 적절히 바꿔보자.
간단한 조합 계산을 하면 풀린다.
제목 그대로 다항 계수를 구하는 문제이다.
생성함수를 공부해보려고 풀어봤다. 생성함수 너무 어렵다.. 흠 문제를 더 풀어봐야 하는데 또 유기했군 물론 얘는 생성함수가 아니어도 풀린다고 한다.
$i$번째 돌의 색이 $A_i$인 돌을 순서대로 계속 채울 때, 앞서 $A_i$인 색의 돌이 있었다면 그 사이 구간의 색을 전부 $A_i$로 바꾼다. 이걸 온라인으로 처리하시오.
무난한 스택문제. JOI의 골드는 어떤 맛인가 궁금해서 풀었던듯.
문제에서 주어진 조건을 만족하도록 최소 개수의 정점을 고르는 문제.
영향력이 대충 삼각형 모양이라고 생각하면 정렬하고 그리디하게 뽑아낼 수 있음을 알아낼 수 있다. JOI의 골드는 어떤 맛인가 궁금해서 풀었던듯 2.
정점에 가중치가 있는 트리가 주어진다. 고양이가 처음에는 가중치가 가장 큰 정점에 위치하고, 다음의 행동을 할 수 있다.
- 정점에 장애물을 놓는다.
장애물을 놓았을 때, 해당 정점에 고양이가 없다면 아무 일도 일어나지 않고, 고양이가 있다면 고양이가 장애물이 있는 정점을 지나지 않고 도달 가능한 정점 중 가중치가 가장 큰 정점으로 최단거리로 이동한다. 이때, 고양이의 이동 횟수를 최대화하라.
잘 생각해보면, 가중치가 $a$인 곳에서 $b$인 곳으로 가려면, 해당 경로에 $b$ 미만인 값들만 존재하면 된다. 따라서 역으로 가중치가 작은 정점부터 유니온파인드 등의 자료구조를 사용하여 이동거리, 현재위치를 담아 합쳐나간다면 LCA등을 이용하여 합쳐줄 수 있다.
[BOJ 24002] Trapezoid Counting
막대 길이들이 주어질 때, 이 중 $4$개의 막대를 골라 이등변 사다리꼴이 되는 경우의 수 구하기. 단 여기서 사다리꼴은 평행한 변이 한 쌍인 볼록사각형으로 간주한다.
재밌는 줄 알았는데 재미 없었던 문제.
각 길이들을 카운팅해두고, $[a, a, a, b]$인 쌍과 $[a, a, b, c]$인 쌍을 대소비교 잘 해주면서 열심히 세주면 풀렸던것 같다.
미술품은 각각 (크기, 가치)를 가지고 있다. 미술품 여러개를 골라, (가치의 합)-(가장 큰 크기-가장 작은 크기)를 최대화하라.
대충 작품이 크기 순서로 정렬되어 있다고 하고, $i$번 작품의 크기를 $A_i$, 가치를 $B_i$라고 하자. $A_i < A_j$인 두 작품 $(i, j)$를 고른다면 당연히 $A_i < A_x < A_j$를 만족하는 $x$들은 전부 선택하는게 이득이므로, 누적합을 써보고 싶어진다.
$1$번부터 $i$번 작품까지의 작품의 가치의 합을 $S_i$라고 해보자. 그럼 이제 문제는 $S_j - S_{i-1} - (A_j - A_i)$가 가장 큰 $(i, j)$쌍을 구하는 문제가 된다. $S_j - A_j$는 고정값이므로, $S_{i-1}-A_i$의 최솟값을 들고다니면 빠르게 계산해줄 수 있다.
문제 출제도 했다. 많관부.
먼저, $N$의 값에 따른 가능한 답의 상한을 구해봅시다.
격자에 채워져 있는 모든 정수의 합을 $S$라고 정의하겠습니다. 그렇다면 $\sum_{i=1}^{N} {R_i} = S$, $\sum_{j=1}^{N} {C_j} = S$이므로 $\sum_{i=1}^{N} {R_i} + \sum_{j=1}^{N} {C_j} = 2S$입니다. $\operatorname{mex}$ 계산에 사용되는 값의 개수는 $2N$개입니다. 만일 정답이 $2N$이라면, $R_i$와 $C_j$들은 $0$부터 $2N-1$까지의 값을 하나씩 가져야 합니다. 이때 $\sum_{i=1}^{N} {R_i} + \sum_{j=1}^{N} {C_j} = \frac{(2N)(2N-1)}{2} = N(2N-1)$이 되는데, $N$이 홀수라면 $N$과 $(2N-1)$이 홀수이기 때문에 $N(2N-1)$이 홀수입니다. 이는 모순이므로 $N$이 홀수인 경우 답이 $2N$이 될 수 없습니다.
이제 $N$이 짝수인 경우 답이 $2N$인 격자를, 홀수인 경우 답이 $2N-1$인 격자를 구성할 수 있다면 그것이 최적해가 됩니다. 실제로 두 해를 모두 구성할 수 있으며, 그 예시 중 하나는 다음과 같습니다.
[BOJ 23725] Handing out Balloons
누가 풀던걸 뺏어풀었다.
$N$개의 기둥이 있고, 각 기둥에 풍선이 $b_i$개씩 달려있다. 아이들이 오면 가장 앞에 위치한 풍선이 남아있는 $3$개의 기둥에서 풍선을 하나씩 빼서 준다. 기둥을 적절히 배치해서 최대한 풍선을 많이 주는 개수를 구해보자.
잘 생각해 보면, 그냥 $N$개의 기둥을 $3$개의 그룹으로 분할해서 각 그룹의 합의 최솟값을 최대화하는 것과 동치임을 알 수 있다.
하지만 $DP(i, j, k, l) :=$ $i$번 기둥까지 봤고, 각 그룹의 합이 각각 $j$, $k$, $l$인 경우로 놓으면 시간복잡도가 너무 크기 때문에 한 가지 트릭을 쓸 수 있는데, 바로 풍선의 총합은 일정하기 때문에 $l$을 저장하지 않아도 $l$의 값을 알 수 있다는 것이다.
따라서 이걸 잘 짜주면 된다. 근데 제한조건상 $T$가 너무 커서 데이터를 최악으로 만들면 아마 터질텐데, 그냥 조건을 대충 만든 것 같다. 공식 데이터 보면 엄청 허술함
마법사가 책을 읽는데, 초기 즐거움은 $0$이고, $i$번 책을 읽으려면 즐거움을 $a_i$만큼 소모한 뒤 $b_i$만큼의 즐거움을 얻는다. 즐거움이 음수가 되면 망할때, 모든 책을 다 읽을 수 있을까?
$a_i \le b_i$라면 $a_i$가 작은 책들부터 읽어서 최대한 차이를 만들어놓는게 이득이고, $a_i > b_i$라면 어차피 모든 책을 언젠가는 읽어야 하기 때문에 $a_i$가 큰 책부터 해치우는게 좋다. 이렇게 두고 그리디 돌려서 가능불가능 판정하면 된다.
$2 \times 2 \times 2 \times 2 \times n$크기의 5차원 격자를 $1 \times 1 \times 1 \times 1 \times 2$로 타일링하는 문제.
벌캠을 알면 쉽다. 5차원 격자에서 인접한 칸을 어떻게 찾나요? 라는 질문이 있을 수 있는데, 정확한 명칭은 까먹었지만 차원 확장을 비트 개념으로 할 수 있다.
0차원 -> 1차원을 점 2개를 찍어서 이어주고, 1차원 -> 2차원 확장을 선 2개를 그어서 대응되는 점끼리 이어주고, 2차원 -> 3차원 확장을 면 2개를 그려서 대응되는 점끼리 이어주고.. 이런게 가능하다.
근데 이 대응된다는 개념을 해당 위치의 비트가 켜지고 꺼진걸로 할 수 있는데, 이걸 이용하면 5차원에서 인접한 칸을 다음과 같이 구해줄 수 있다.
for(int i=0; i<16; i++){
for(int j=0; j<16; j++){
if(__builtin_popcount(i^j) == 1){
m[i][j] = m[j][i] = 1;
}
}
}그럼 이제 이걸 통해서 dfs등을 돌려 작은 범위에서 DP전이를 계산하여 값을 뽑아낼 수 있고, 벌캠을 돌리면 된다.
항은 대충 넉넉하게 200개정도 뽑으면 돌고, 로컬에서 10초정도 걸렸다.
[BOJ 15292] Journey from Petersburg to Moscow
어쩌다 이런 문제를 잡았지..? 아하 클래스 문제군요
양방향 그래프가 주어질 때 $1$번 정점에서 $N$번 정점으로 가는 최소 비용 구하기. 단, 이때 비용은 가중치가 가장 큰 $k$개의 간선에 대해서만 계산된다.
가중치가 $x$인 간선이 $k$번째 간선이었다고 해봅시다. 그러면 다음과 같이 문제를 바꾸어 풀 수 있습니다.
모든 간선의 가중치를 $\max (w_i - x, 0)$으로 바꾸고 다익을 돌립니다. 이때 얻은 비용에 $x \times k$를 곱해주면 그 시점에서의 최소 비용이 됩니다.
이걸 편하게 짜려면 간선을 가중치 순으로 정렬해두고 잘 돌리면 됩니다. 한 가지 주의할건 $k$개의 경로를 전부 지나지 않을 수 있으므로, 처음에 다익을 한 번 돌리고 시작해야 한다는 점 정도?
aliens 트릭을 공부하려고 했는데 뭔가 잘 안되길래 화가나서 그냥 재밌어보이는걸 풀었다.
구슬이 $2^a+2^b+2^c+2^d$개 있다. 처음에는 구슬 전체가 한 더미고, 이걸 모두 크기 $1$짜리 더미로 나누어야 한다. 나누는 연산은 $x = y+z$를 만족하는 $(x, y, z)$쌍으로 할 수 있으며, 이때 크기가 $x$인 모든 그룹이 크기가 $y$, $z$인 두 개의 그룹으로 쪼개진다. 최소 횟수로 쪼개시오.
일단 조건에 의해 주어지는 전체 구슬의 개수를 비트로 나타내면 비트가 $1 \sim 4$개 켜져 있는 수이다. 한 번의 연산을 통해 비트 하나를 떼어낼 수 있기 때문에, 비트가 $p$개 켜져 있고 최상위 비트가 $q$번째라면 일단 $q-1+p$번의 시행으로 문제를 해결할 수 있다. 이보다 횟수를 줄일 수 있는 경우는 비트가 $4$개 켜져 있는 경우가 유일한데, 몇가지 관찰을 해야 한다.
- $3$으로 나누는 것이 이득일 수 있다.
- 만약 주어진 수 $A$가 3의 배수라면, $A = \frac {A} {3} + \frac {2A} {3}$, $ \frac {2A} {3} = \frac {A} {3} + \frac {A} {3}$의 2번의 시행으로 $3$으로 나눌 수 있다.
- 이것이 손해를 보지 않으려면 $3$으로 나눈 값의 최상단비트가 $2$칸 줄어들어야 하고, 켜진 비트의 수가 $4$개보다 커지면 안 된다.
- 비트를 둘 씩 분리하여 잘 깎다보면 한 번 이득이 생길 수 있다.
- 예를 들어, $A = 110011_2$라면, $A$를 $110000_2$와 $11_2$로 분리한 뒤, $110000$을 $11$까지 깎아 진행하면 이득을 볼 수 있다.
- 여기서 케이스가 하나 더 있는데, $A = 101011_2$같은 수를 보면 $101000_2$과 $11_2$로 분리한 뒤 $101000_2$을 $101_2$까지 깎고 나면 $101_2 = 11_2 + 10_2$, $11_2 = 10_2 + 1_2$, $10_2 = 1_2 + 1_2$로 이득을 볼 수 있다.
위 내용들을 잘 처리하면 AC를 받을 수 있다.
$s$로 시작해서 $f$로 끝나는 길이 $N$의 zig-zag순열의 개수를 구하시오.
Connected Components DP라는게 있길래 공부해봤다. 이게 뭐냐면 이제 $1$부터 $N$까지 순서대로 순열에 삽입해서 경우의 수를 셀 건데, $i$까지 넣었을 때 Connected Components의 개수가 $j$임을 저장하는 것이다.
새로운 수를 삽입할 때, 다음의 경우들을 생각해 볼 수 있다.
- 새로 삽입하는 수를 독립된 컴포넌트로 취급한다.
- 이는 컴포넌트의 개수에 의해 구간이 분리되기 때문에, $DP(i, j) = DP(i-1, j-1) \times j$와 같이 전이된다.
- 새로 삽입하는 수를 기존에 존재하는 컴포넌트의 우측 혹은 좌측에 붙인다.
- 여기서 생각해보아야 할 점은, $i$는 항상 증가하는 순서로 넣고 있기 때문에 어떠한 컴포넌트의 한쪽에 붙이게 되면 그 시점에서 이번에 넣은 값이 옆에 있는 값보다 항상 크다. 그런데 넣은 위치가 순열의 양 끝이 아니라면 옆에 더 큰 무언가가 와야하고, 그럼 zig-zag가 깨진다.
- 또한, 양 끝은 $s$혹은 $f$가 채워져야 하므로 불가능하다. 따라서 이 케이스는 무시한다.
- 새로 삽입하는 수를 기준으로 양쪽의 컴포넌트를 합친다.
- 이 경우 새로 삽입하는 수가 양쪽의 컴포넌트에 속한 값보다 클 것이고, zig-zag가 유지되므로 올바른 삽입이다. 따라서 $DP(i, j) = DP(i-1, j+1) \times j$와 같이 전이된다.
$s$ 또는 $f$는 삽입 위치가 고정이고, 이 수들이 삽입된 시점부터 $DP$전이가 약간 바뀌는 것만 고려해주면 답을 구할 수 있다.
자구 공부하려고 자구 태그를 밀려고 했는데,,흠 그냥 히가큰직이다.
세그 짜기 싫어서 유파로 밀었다.
나무를 심으면 지금까지 심어진 나무들과의 거리의 합만큼의 비용이 발생하고, 매번 발생한 비용들의 곱을 구하시오.
지금까지 심어진 나무들의 원점으로부터의 거리의 합과 특정 구간에 위치한 나무들의 개수를 알 수 있다면 답을 빠르게 계산해줄 수 있다. 합세그, 카운트세그 2개 선언해서 풀었다.
각 사람이 자신의 앞에 위치한 사람들 중 자신보다 키가 작거나 같은 사람의 수를 알려줄 때, 각 사람의 키를 구하시오.
값이 가장 작은 사람 중에서 인덱스가 가장 큰 사람은 키가 가장 작을 것이다. 걔를 구하고, 걔의 뒤에 위치한 사람들은 전부 얘보다 키가 클 것이므로 뒤 구간의 모든 값을 $1$빼준다. 이걸 해주는 레이지세그로 밀었다. 태그 보니 이분탐색이 많던데 잘몰루
[BOJ 18431] Just Long Neckties
길이가 $N+1$인 배열 $A_1, A_2, \cdots, A_{N+1}$과 $B_1, B_2, \cdots, B_N$이 주어진다. $A_1$부터 $A_{N+1}$까지 하나씩 밴했을 때, 각각의 경우에 대해 $A_i$와 $B_j$를 일대일 매칭시켜서 $\max (A_i-B_j, 0)$의 최댓값의 최솟값을 구하시오.
하나가 밴되면 둘 다 정렬해놓고 매칭하는게 최적일거고, 밴되는게 바뀔 때 바뀌는 값이 몇 개 없기 때문에 multiset을 이용해서 다 들고다니면 된다. 근데 풀이가 여러가지 있는듯?
J, O, I가 순서대로 $K$번씩 나오는 문자열을 만들고 싶은데, 앞 또는 뒤의 문자를 삭제하는건 코스트가 없다. 최소 코스트를 구해보자.
O의 개수가 $K$이도록 투포인터 비스무리한걸 짜고, 양쪽 구간에서 각각 J가 $K$개, I가 $K$개가 되는 지점을 이분탐색으로 찾으면 풀린다. 구현이 좀 귀찮은듯
[BOJ 18433] Collecting Stamps 3
원형으로 된 구조가 주어진다. $i$번 스탬프는 원점으로부터 $X_i$거리에 있으며 $T_i$초 후에 사라진다. 최대 몇 개의 스탬프를 수집할 수 있겠는가?
그냥 읽자마자 자명한 DP가 떠오른다. 원점을 중심으로 시계방향으로 $i$번째 스탬프, 반시계방향으로 $j$번째 스탬프를 가져간다면 그 사이 스탬프들은 당연히 거쳐가게 된다. 따라서 저 $2$개의 변수랑 시계방향에서 끝났는지, 반시계방향에서 끝났는지의 정보를 담는 세제곱 DP를 열심히 짜면 된다. 구현이 좀 어려웠다.
누가 자꾸 재밌다고 하시길래 풀어봤다. 재밌긴 했다.
길이 $N$의 순열들 중에서 사전순으로 가장 앞서는 길이 $M$의 순열이 주어진 순열과 동일한 순열의 경우의 수를 세면 된다.
$X_1 < X_2 < \cdots < X_k$를 만족하는 최대의 $k$를 찾자. $X_k$까지는 $X_{k-1}$까지의 구간에서 자신보다 작은 수가 오면 안 된다. 이걸 작은 수 부터 위치를 결정해주면 들어갈 수 있는 위치의 수를 바로 알 수 있으며, $X_{k+1}$이후의 수들을 고려해서 모든 수가 배치 가능한지 판별해주고 경우의 수를 잘 세주면 된다.
방향그래프가 주어지고, 간선 딱 하나의 방향을 바꿀 수 있을 때 왕복 최단 경로를 구하는 문제.
대충 모든 간선을 다 뒤집어서 답을 구해보고 싶다. 최단경로를 구해두고, 최단경로가 해당 간선을 지나는지 여부에 따라 답을 갱신해주면 된다..가 풀이의 전부인데 좀 생각을 잘못하면 구현이 이상해진다. 나름 고생한 문제
모 대회의 문제를 검수하기 위해 가져온 템플릿으로 날먹했다.
모 대회의 문제를 검수하기 위해 가져온 템플릿으로 날먹했다 2.
2차원 격자가 주어질 때, J를 기준으로 우측에 O, 아래쪽에 I가 있는 (J, O, I)쌍의 수를 구하시오.
가로로 O의 개수 누적합, 세로로 I의 개수 누적합을 해두고 J의 위치들에 대해 답을 더해주면 된다.
그림 $i$의 크기는 $S_i$이고, 가치는 $V_i$이다. 크기 $C_i$인 액자에는 크기가 $C_i$보다 작거나 같은 그림만 넣을 수 있고, 액자는 비내림차순 정렬, 가치도 비내림차순 정렬이 되어야 할 때 전시할 수 있는 그림의 수 구하기
액자는 $C_i$기준으로 정렬하고, 그림은 $S_i$기준으로 정렬한 뒤 뒤에서부터 $V_i$ 비교해가면서 그리디하게 배치해주면 된다.
[BOJ 16982] Growing Vegetables is Fun 3
R, G, Y로 이루어진 문자열을 인접한 문자가 같지 않도록 배치하기까지 최소 swap횟수 구하기. swap은 인접한 두 문자 바꾸는 것이다.
$i$번 문자까지 배치했고 $R$, $G$, $Y$를 각각 몇 개 배치했는지로 $DP$를 전이하면 그냥 풀린다. 이게 왜 다이아?
[BOJ 12686] King (Large), [BOJ 12685] King (Small)
순서대로 킹을 움직여서 더 이상 움직이지 못하면 진다. (이전에 방문한 칸과 #으로 칠해진 칸은 못간다) 누가 이기는지 구하시오.
유명한 문제의 일반 그래프 버전. 위에 있는 일반적인 매칭의 개수를 킹이 있는 칸을 포함할 때와 포함하지 않을 때 2번 구해서 비교하면 된다.
대충 백준은 검수한거 몇개 빼고 다쓴거같고,, 코포는 쉬운거 위주로 엄청 많은데 쓸지 말지 생각을 좀 해보죠
'Problem Solving > boj' 카테고리의 다른 글
| [BOJ 15107] Rainbow Roads (0) | 2026.02.13 |
|---|---|
| 기록용 (0) | 2025.10.24 |
| [BOJ 33160] 꽃 풀이 (0) | 2025.01.16 |
| 2025. 01. 14 (2) | 2025.01.15 |
| 2025. 01. 13 플랜디 (2) | 2025.01.14 |