leo020630의 블로그

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)\)으로 주어진 조건을 만족하는지 확인할 수 있다...

블로그 주인의 PS 경력에 대한 소개글입니다. 계속 수정됩니다.e-mail: leo020630@naver.com[프로필]BOJ- leo020630 (2896 Solved, Ruby V - 2751,  POSTECH #1)Codeforces - leo020630 (Max Rating : 2302, International Master)Atcoder - leo020630 (Max Rating : 2029, 1 Dan)CodeChef - leo020630 (Max Rating : 2358, 6★) [소속][2018~2020] 경기북과학고등학교 3학년 졸업[2019] 경기북과학고등학교 알고리즘 동아리 ALPS 기장[2021~] 포항공과대학교 재학[2022] 포항공과대학교 알고리즘 동아리 POSCAT 회장[202..

이번 주말은 유독 칠 대회가 많았다. 총 앳코더 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\)까지 돌리면 되니 오버플로우는 고려할 필요가 없으며, 예외처리..

분명히 작년에 ICPC를 같이 나갔지만 놀랍게도 처음인 팀 연습이다. slah007, qjatn0120 선배와 함께 진행하였다. 셋은 BAPC 2018 예선을 사용하였다. ~00:00 동아리 부원들의 실력 증진 차원에서 팀 연습을 함께 진행하였는데, 여러가지 issue로 인해 예정보다 10분 늦게 시작하였다. 내가 A~D, qjatn0120 선배가 E~G, slah007 선배가 F~K를 잡기로 했다. 00:10 A가 좀 화나게 생기긴 했지만 문제 자체는 간단하다는 것을 깨닫고 바로 짜 AC를 받았다. 5분 후에 H 역시 AC가 나왔다. 00:26 영어 지문을 읽는 데에 조금의 애로사항이 있었지만, 다 읽고 나니 B도 쉬웠다. 쉽게 짜서 AC를 받았고, 거의 동시에 E도 AC가 나왔다. 00:39 J AC..

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

이 사이트에 가입한게 8년이 다 되어 가는데, 1000솔을 이제서야 했다. 최근에 동아리 세미나 연습 문제 선정을 비롯해서 문제 풀 일이 좀 있었고, 개강을 하니까 공부하는게 진짜 너무 싫어서 백준을 좀 많이 풀었다. 푼 문제 종류는 주로 단계별로 해결하기 문제들이고, 가끔 랜덤 플레 문제 + 눈여겨보았던 웰노운성 플&다 문제를 위주로 풀었다. 2주동안만 거의 100문제 가까이를 푼 거 같은데, 그러다 보니 문제 수도 꽤 차고, 웰노운성 플&다 문제 중 클래스 8에 포함된 문제가 꽤 있었다. 오늘 오후에 확인해보니 1000솔까지 남은 문제 수와 클래스 8 취득을 위해 남은 문제 수가 4개로 똑같길래 적당히 풀이를 아는 문제 (또는 공부해보고싶었던 문제) 3개를 잡아서 풀고 마지막 1000번째 문제를 뭐로..

대회중 과정과는 상관 없이, 에듀만 치면 결과가 귀신같이 좋다. 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