leo020630의 블로그

카테고리 제목이 PS인데 너무 CP만 다룬 것 같아서 최근에 푼 백준 문제들 중 인상깊었던 것들을 정리해서 쓰려고 한다. 세미나를 준비하면서 백준에 있는 행렬 DP 문제는 거의 몽땅 푼 것 같다.. 이번에 정리할 문제들도 모두 여기에 속하는 것들이다. 2086 - 피보나치 수의 합, 11440 - 피보나치 수의 제곱의 합, 11778 - 피보나치 수와 최대공약수 모종의 정리들을 알거나 규칙을 찾으면 평범한 피보나치 수 문제로 환원할 수 있다. 2086은 규칙을 찾아서 풀었고, 뒤의 두 개는 적당히 검색해서 풀었다. 17401 - 일하는 세포 보자마자 풀이는 보이는데, 구현이 좀 귀찮은 문제이다. 신경써야 할 점은 1. 같은 행렬을 거듭제곱하는 문제들과는 다르게 교환법칙이 통하지 않는다. 2. 주어진 행렬..

열심히 풀고 기여를 하러 갔는데, 다들 내 풀이와 방향성이 다른 것 같았다. 정해가 시간 복잡도 면에서도, 난이도 면에서도 조금 더 낫지만 내 풀이도 의미가 있다고 생각해 적어보려 한다. 해당 풀이는 7469 - K번째 수를 PST로 푸는 방법을 트리로 확장시켜 적용한다. 간단하게 요약을 하자면, 인덱스 순으로 세그트리를 $N$개 만든 후 $R$번째 세그트리에서 $L-1$번째 세그트리를 뺀 값으로 세그 이분탐색을 해서 K번째 수를 찾는다. (이 과정에서 배열의 각 수에 대해 좌표압축을 해 주어야 한다.) 세그 이분탐색이란 왼쪽 자식의 합과 K를 비교해 K가 크면 오른쪽, 그렇지 않으면 왼쪽으로 가는 작업을 반복하는 것을 말하며, 세그트리를 여러 개 만드는 것은 PST를 통해 수행할 수 있다. ..

A. Red Versus Blue (0:02, +) R/(B+1)개와 R/(B+1)+1개를 적절히 배치해주면 된다. B. Bit Flipping (0:16, +) 앞에서부터 그리디하게 설정해주면 되는데.. 구현 미스가 나서 좀 오래 걸렸다. C. Line Empire (0:40, +) 끝 위치가 $x$라면, 그 전까지는 계속 옮겨주는 것이 최적이다. 이를 각 경우에 대해 계산해주면 된다. D. Reverse Sort Sum (1:06, +) 우선 주어진 배열의 평균을 통해 1의 개수를 구해준다. 이후, 뒤 원소부터 보며 자명하게 결정 -> 1의 개수에 따라 업데이트를 반복해주면 문제를 해결할 수 있다. Range Update Point Query 펜윅트리를 사용하면 $O(NlogN)$에 문제를 해..

A. Lacked Number (0:01, +) *22 B. Slimes (0:02, +) *41​ 생략 C. Dice Sum (0:05, +) *787 C번치고 어려워서 놀랐다. $DP[i][j]$를 i번째 주사위까지 봤을때 합이 j인 경우의 수로 정의하면 $O(N^4)$ 정도에 문제를 해결할 수 있다. D. Range Count Query (0:06, +) *793 같은 숫자들에 대해 등장하는 인덱스를 벡터에 저장해 준 후 lower bound와 upper bound를 적절히 사용해 개수를 구해주면 된다. E. K-colinear Line (0:15, +) *1292 고려해야 하는 직선의 개수가 $O(N^2)$개이고, 이에 대해 $O(N)$으로 주어진 조건을 만족하는지 확인할 수 있다...

이번 주말은 유독 칠 대회가 많았다. 총 앳코더 2개, 코포 2개, 구글 코드잼 1A 라운드가 있었는데, 코드잼은 자느라 못쳤고, 앳코더는 (실력적으로) 못 쳤기 때문에 특별히 잘 친 2개의 코드포스 라운드를 정리해보도록 하겠다. Codeforces Round #781 (Div. 2) A. GCD vs LCM (0:00, +) 보자마자 답이 보여서 짜서 냈다. 덕분에 코포하면서 처음으로 500점을 먹을 수 있었다. ㅎㅎ B. Array Cloning Technique (0:05, +) 가장 많이 등장하는 수의 개수를 센 후, 적당히 2배씩 하면서 횟수를 구해주면 된다. C. Tree Infection (0:33, +3) 킹받는 그리디 문제이다. 우선 노드를 Sibling 단위로 묶으면 트리와 관계 없는 ..

앳코더는 레이팅이 잘 오르는 것 같다. 아직 낮아서 그런가? A. Four Prints (0:01, +) *28 직사각형의 세 꼭짓점이 주어졌을 때 남은 하나의 점을 구하면 된다. 적당히 if문을 써주면 구현할 수 있다. A번치고 오래 걸렸다. B. Get Closer (0:03, +) *79 구하라는 것을 계산하면 된다. 문제에서 제한을 상당히 편하게 주어 대충 짜도 된다. C. Coupon (0:07, +) *336 $A_{i}/X$의 합과 $K$를 잘 비교해 처리해주면 된다. D. 2-variable Function (0:30, +3) *1148 $A$를 고정한 후 $B$는 이분 탐색으로 찾아주면 된다. 최대 $10^6$까지 돌리면 되니 오버플로우는 고려할 필요가 없으며, 예외처리..

앞으로 어떤 방식으로던 하루에 문제를 많이 푼 날에는 이렇게 정리글을 작성하려 한다. 사실 그냥 여러개의 CP 글을 따로 쓰기 귀찮아서 하나에 합치는 것 같기도 하다. 오늘은 백준 나코더 입부테스트 Open이랑 ABC를 쳤다. 2022 IamCoder Qualification Test Open A. 카드 색칠 (00:20, 3 try) 적당한 난이도의 Constructive 문제다. 연속된 0의 구간을 잘 칠해주면 되는데, 난 잘 생각이 안나서 좀 더럽게 풀었다. B. 개표 (00:31, 2 try) 조건은 간단한 수식으로 나타낼 수 있다. 그 과정에서 나는 각 후보의 득표수를 multiset으로 관리했는데, 어차피 받는 표가 양수기 때문에 그냥 변수 하나로 관리하면 된다고 한다. C. Split the..

대회중 과정과는 상관 없이, 에듀만 치면 결과가 귀신같이 좋다. A. Integer Moves (00:01, +) 주어진 점이 원점이면 0, 원점과의 거리가 정수면 1, 아니면 2이다. B. XY Sequence (00:03, +) 그리디하게 해주면 된다. C. Bracket Sequence Deletion (00:18, +) 괄호 문자열에서 팰린드롬을 생각해본건 처음이라 뇌절이 와 지문을 좀 느리게 읽었다. 만약 앞 두 글자가 ((이나 ))인 경우 팰린드롬이라 지울 수 있고, ()인 경우 올바른 괄호 문자열이라 지울 수 있다. 남은 경우는 )(인데, 이 경우 )(((..(()가 팰린드롬이므로 )가 다시 나올때까지 확인해주면 된다. D. For Gamers. By Gamers. (01:11, +7) 핵심..

코포랑 앳코더가 같이 있었는데, 코포가 테크노컵+앳코더 블루까지 레이팅이 얼마 남지 않았었기 때문에 앳코더를 쳤다. 결과적으로는 괜찮은 선택이었던 것 같다. A. Last Letter (0:00, +) *6 B. Go Straight and Turn Right (0:02, +) *30 생략 C. Yamanote Line Game (0:04, +) *165 앳코더에서는 처음 보는 인터랙티브였다. 하지만 인터랙티브인게 별 의미가 있는 수준은 아니었고, set등을 이용해 구현하면 쉽게 맞을 수 있다. D. Swap Hats (0:08, +) *165 D번 정도면 꽤 귀찮다는 인식이 있었는데, 너무 쉬워서 놀랐다. 두 배열의 inversion parity가 일정해야 하는데, n이 3이니 대충 if문으로 구현해주..

랜덤 플레 디펜스를 하다 풀게 된 문제이다. 오렌지 컵 문제인데, 에디토리얼도 아직 없고 구글링했을 때 풀이가 나오지 않길래 내가 적어보려 한다. 앞으로도 푼 백준 문제들 중에 자료가 없는 것들은 이렇게 풀이를 작성할 예정이다. 문제 요약 오렌지 농장에 $N$개의 오렌지를 심을 수 있는 지점이 있다. 오렌지는 심은 후 $k$초가 지나면 수확이 가능하다. 모든 지점에 오렌지를 심고 모든 지점에서 오렌지를 수확하기 위한 최소의 시간을 구하여라. 풀이 $DP[i]$를 $i$번째 오렌지까지 모두 수확하고 i번째 지점에서 멈췄을 때의 최소 시간으로 정의하자. 그러면 다음과 같은 점화식을 통해 $DP[i]$를 구할 수 있다: \(DP[i]=min_{0