woojin042의 블로그

기록용으로 짧게 후기를 남깁니다. 1. 거스름돈 (그리디, 시뮬레이션)시간에 따라 생기는 돈의 개수를 시뮬레이션으로 관리해주면 되는 쉬운 문제이다. 이 때 화폐의 가치가 배수 관계이므로 단위가 큰 돈을 먼저 쓰는 게 항상 최적임을 알 수 있다. 예상 난이도: B1-S5 2. 폭탄 (DP)dp(n, dir): 지금까지 1~(n-1)번째 폭탄을 처리했고, 현재 (dir==0 ? 0 : L) 좌표에 있을 때 남은 폭탄들을 처리하기 위한 최소 이동거리로 두면 상태를 쉽게 전이할 수 있다. 예상 난이도: S3-S2 3. 십진수 (수학)digit dp 느낌의 수학 문제이다. 앞자리 수부터 보면서 3의 거듭제곱 꼴을 답에 계속해서 더해주면 된다. N의 모든 자릿수가 2보다 작거나 같은 경우 예외 처리를 잘 해 ..

서론5월에 개최된 포스텍 프로그래밍 경진대회에 '트랄랄레로 트랄랄라'라는 팀명으로 참가했습니다.(문제 링크, 에디토리얼) 2025 프로그래밍 경진대회(PPC) 성료 | 컴퓨터공학과뉴스 홈으로 소식 뉴스 COMPUTER SCIENCE AND ENGINEERING COMPUTER SCIENCE AND ENGINEERINGCOMPUTER SCIENCE AND ENGINEERING COMPUTER SCIENCE AND ENGINEERINGcse.postech.ac.kr 작년 PPC는 분반 엠티가 겹쳐서 참가하지 못했다. 그래서 올해가 교내대회 첫 출전이다. 같이 나갈 사람이 없어서 큰 고민이었는데, 동아리 회식 때 순진하고 백준을 잘 푸는 새내기 두 명(chansolpark7, taey1015)을 발견해 ..

https://www.acmicpc.net/problem/33960 PPC 2025 본 대회에서 끝내 못 푼 문제. 자신있는 DP 문제인데다가 이 문제만 풀면 1등 팀과 솔브수가 같은 상황이었는데... 못 풀어서 아무쪼록 한이 맺힌 문제이다.점화식은 간단하지만, 떠올리기가 어렵고 증명하기도 어려운 문제인 것 같아 풀이를 정리해본다. 아래보다 더 쉬운 증명이 있는지는 잘 모르겠다. 구간 DP를 이용하여 푼다. $dp[l][r]$: 구간 $[l, r]$에서 얻을 수 있는 점수의 최댓값이라 두자.Claim: 어떤 $l \le i $$ dp[l][r] = dp[l][i] + dp[i+1][r] + score(l, i, r) $$이 성립한다. 이 때 $score(l, i, r)$은 구간 $[l, i], [i+..

셋: https://codeforces.com/contest/2085A. Serval and String Theory$k=0$인 경우, $s$가 universal이기 위해서는 처음부터 original $s$가 한 종류의 문자로만 이루어져 있을 경우, 답은 항상 불가능이다.그 외의 경우 항상 $s$를 universal하게 만들 수 있다. 양 끝 문자가 다르다면 그 둘을 swap하면 되고, 양 끝 문자가 같으면 다른 곳에서 문자를 하나 가져와 양 끝 문자 중 적절한 것과 swap하면 되기 때문이다.int n, k;string str;cin>>n>>k>>str;string rev = str;reverse(all(rev));if(rev > str || str[0]!=str[n-1] && k>0){ cout..

시험도 끝났겠다 오랜만에 유사코 연습을 돌렸다.어려운 문제를 푸는 연습을 해야 할 것 같아서 셋은 골드 셋으로 골랐다. 내년에도 ICPC를 광탈하지 않기 위해서는 골~플랜디를 더 빡세게 할 필요가 있을 것 같다. 중간에 HLD 템플릿 만든 시간을 빼면 두 시간 정도 걸려서 풀었다. 확실히 유사코는 순수 애드혹/그리디의 비중은 낮고 여러 가지 자료구조와 알고리즘을 사용하는 문제가 많이 출제되는 것 같다. 18262: Milk Pumping (G1, dijkstra) 방향 그래프가 주어지고, 1번 정점에서 시작해 $n$번 정점에서 끝나는 경로 중 (경로의 유량) / (경로의 가중치 합)의 최댓값을 찾는 문제이다. 고정된 $k$에 대해 유량이 $k$ 이상이 되도록 최단 경로를 구성하려면 유량이 $k$ 이상인 ..

https://www.acmicpc.net/problem/3090 그리디 + 파라메트릭 서치를 사용하는 문제이다.문제를 풀고 블로그 풀이들을 보는데 내가 푼 방법이랑 많이 달랐고, 하나같이 이걸 어떻게 생각함(...) 식의 풀이여서 글을 쓰게 되었다.(시험 기간에 공부하기 싫어서 쓴 것도 있다.) 우선 보자마자 파라메트릭 서치를 쓰면 좋을 것 같다는 생각이 들었다.인접한 원소 간 차이의 최댓값을 한 번에 최소화하는 것보다, 인접한 원소 간 차이가 어떤 $d$ 이하가 되도록 연산을 수행할 수 있는지 판별하는 게 더 쉬워 보였기 때문이다. 여기서 한 가지 관찰을 할 수 있는데, 배열 $A$의 최소 원소를 $m$이라 두면, 연산을 최적으로 수행하고 얻은 결과 배열의 모든 원소는 $m$보다 크거나 같다.이는 ..

딱히 재미도 감동도 없는 셋이였다...  10021: Watering the Fields (G3, mst) MST 기본 문제이다. 필요한 간선만 만들어서 mst로 슥삭해주면 된다.  10022: The Lazy Cow (G4, 누적 합) 그나마 재밌었던 문제이다. 어떤 시작점으로부터 맨해튼 거리가 $K$ 이하인 점들의 값 합을 최대화하는 문제인데 제한이 작아서 브루트포스를 돌리면 된다. 맨해튼 거리의 contour는 다이아몬드 모양으로 구현이 불편하기 때문에, 45도 돌려서 체비쇼프 거리 꼴로 변환하여 2차원 정사각형 누적합의 최대를 구해주면 된다. 거리 변환 시 빈 공간이 생기는데, 시작점이 빈 공간이 되지 않도록 잘 확인해줘야 한다.  10023: Mooo Mooo (G4, DP) 문제를 잘 변형하면..

골드 셋도 맛보고 싶어서 도전해봤다. 옛날 대회라 그런가 든든국밥 문제들만 나와서 비교적으로 쉽게 풀 수 있었던 것 같다.  5922: Above the Median (P4, Segment Tree) 젠장 또 median이야!고정된 값 $X$에 대해 주어진 수열의 contiguous subsequence 중 median이 $X$ 이상인 것들의 개수를 구하는 문제이다. $X$보다 크거나 같은 $a_i$를 $1$로 치환하고 $X$보다 작은 $a_i$를 $-1$로 치환하면, 놀랍게도 합이 0 이상이 되는 연속 부분 배열의 개수를 구하는 문제가 된다! 연습 중에는 merge sort tree로 누적 합을 관리하는 방법을 사용했는데 $(N\log^{2}{N})$, 그냥 누적합 배열에서 inversion count..

[공지]https://www.acmicpc.net/group/21869USACO 셋을 밀려고 하는데, 혼자 하긴 적적해서 그룹을 만들었어요!매주 수/금/일 오후에 그룹 내 연습으로 silver~gold 수준의 셋 한 개를 돌아볼 예정입니다.(제 개인 사정으로 몇 번 건너뛸 수도..😢)열심히 하실 분 / 찍먹 하실 분 / 관전만 하실 분들 모두 환영입니다..!  오늘은 2018년 US Open (왜 거창하게 us-open이지..?) silver 셋을 돌렸다. 원래 9시 즈음에 시작하려 했으나 치킨이 일찍 오는 바람에 두 시간 늦춰서 문제를 풀었다 ㅎ시간 안에 올솔했고 재밌는 셋이였던 것 같다!  15760: Out of Sorts (G1, 정렬, 좌표 압축) 버블 정렬을 배열의 전체 범위에서 수행하는데..

https://www.acmicpc.net/group/21869요즘 그룹을 만들어서 시간을 재고 USACO 셋을 밀고 있다. (가입 신청 환영!!)첫 연습셋으로 2023 February Contest의 Silver 셋을 돌렸다. 아직 부족한 게 많은 것 같다. ㅠ  27846: Bakery (P4, 수학, 이분 탐색) 대충 이분 탐색을 돌리면 되겠다는 생각만 가지고 있었는데, 어떻게 이분 탐색을 돌릴 지 몰라 못 풀었다. 삼분 탐색, 2차원 이분 탐색(...) 등 여러 뻘짓을 했다. 쿠키와 머핀을 굽는 데 필요한 시간의 합을 기준으로 이분 탐색을 돌리면, 놀랍게도 부등식이 잘 풀려서 $O(n)$에 판별 가능한 꼴이 된다! 따라서 시간복잡도 $O(N\log{M})$에 문제를 풀 수 있다. ($M$: $t_..