문제 링크 일단 풀이 설명을 하기 전에 자랑을 하나 짚고 넘어가도록 한다. 문제의 지문이 굉장히 난잡하지만, 요약하면 간단하다. 지문 요약1번과 2번 정점이 문제의 중요한 정점이다. 무향, 무가중치 그래프를 다룬다.1번과 2번 정점을 잇는 경로가 존재함이 보장된다. (번역문에는 누락된 조건)1번과 2번 정점을 잇는 최단 경로는 5 이상이다.여전히 1번과 2번 정점을 잇는 최단 경로가 5 이상이도록 간선을 추가할 때, 추가할 수 있는 간선 개수의 최댓값을 구하여라.$2\le V\le 40\,000;$ $0\le E\le 1\,000\,000$. 풀이더보기생각1. 5는 작은 상수다. 조건에 맞게 모델링을 하자!주어진 그래프의 형태는 다음과 같다. a, b, c, d 영역은 주어진 그래프에서 우선적으로 고정 ..

문제 링크 관찰 1. 모든 기울기의 종류가 그렇게 많지 않다.모든 업데이트가 하나의 원소에 대한 것이므로 모든 순간에 대해 가능한 기울기는 최대 $O(n^2 + nq)$이다.따라서, 각 원소를 최대 한 번씩만 삭제하는 것이 가능하다면, 알고리즘은 시간 내에 동작할 것이다.생각 1. $i$번째 산이 볼 수 있는 산 $j$들을 자료구조로 관리하면서, 업데이트 이후 볼 수 없게 된 산들만 잘 골라내서 지우고 싶다.스택 또는 셋으로 관리하고 싶은데, 기울기가 단조 증가하도록 관리되는 것이 자연스럽다.그런데, 셋의 정의가 '볼 수 있는 산들'이기 때문에, 기울기가 증가하는 순서가 곧 인덱스가 증가하는 순서이기도 하다.관찰 2. 셋 내에서 삭제되어야 하는 원소들은 연속되어 있다.$[$기존 높이와 이루는 기울기, 새..

오늘은 좀 빡세게 풀었다. [P3] 2D 큐브(http:boj.kr/22974): 맨 왼쪽 열을 운반용 레일이라고 상상하자. 이제 행을 순서대로 올바르게 쌓아나가면 된다.[P4] 고용(http:boj.kr/5461): 적당히 간단한 그리디 문제였다. 비율을 기준으로 정렬한 배열에서 prefix를 pq로 관리하면서 비교해주면 된다.[P3] 강수량(http:boj.kr/2094): 쉬운 세그 문제다. 왜 P3인지 알 수 없다. 오랜만에 동적 세그로 구현해봤다.[P3] 길의 개수(http:boj.kr/1533) 추천 ♥️: 독특한 문제의 제한을 이용하면 창의적인 풀이를 낼 수 있다.[P2] Senior Postmen(http:boj.kr/10100): dfs 하나로 슥삭슥삭하는 그래프 능지 유형인데, 웬일로 ..

다시 좀 느슨하게 푼 것 같기도 하고..ㅠ [P2] 균형잡힌 직선형 정원(http:boj.kr/5470): 괄호 문자열 풀듯이 그래프를 그리면 할 만 하다. 세로 폭이 2 이하여야 해서 나올 수 있는 그래프의 형태가 한정되어 있는데 이 안에서 digit DP 감성의 무언가를 열심히 짜면 된다.[P5] 광부 호석(http:boj.kr/21279): 뭐.. 스트릭용 때우기이긴 하지만, 올림피아드를 대비하는 학생들은 이런 문제를 세그 없이 슥삭하는 관점이 박혀 있으면 좋다.[P5] 둘이 한 팀(http:boj.kr/33543): Goodbye, BOJ 2025! 현장에서 푼 문제인데, 이 문제 직전의 문제에서 상수 차이로 TLE를 받는 바람에, 이 문제는 선형 풀이를 찾아야 한다는 강박으로 풀다 보니 좀 고되..

오늘도 마음은 6문제를 풀려 그랬는데, 며칠간 항상 보면 아침에 랜디 3문제 돌리고서 오후~저녁 즈음에 밥 약속이 뒤늦게 성사된다. 랜디도 랜디지만 사람은 사회적 활동을 해야 하므로, 흘려보낸 3문제가 아깝진 않다. [P3] The Cow Run(http:boj.kr/5834): 대충 사수아탕이 생각나는 문제인데, 훨씬 쉽다. 그냥 아침 공복으로 먹기 든든한 DP다.[P3] 라운드 로빈 스케줄러(http:boj.kr/12016): NYPC 맛이 살짝 감도는 문제다. 혹은 코포맛? 훈련용으로 좋은 그런 건데 암튼 국밥.[P3] 흔한 수열 문제(http:boj.kr/2787) 추천 ♥️: 뭐.. 흔한 것 같지 않다. 대 한양 새내기 gubshig의 식견에 도움을 받아 해결했다. N이 작은건 알겠는데 그냥 뭘..

빡세게 푸려고 했는데자꾸 눈에 POI - Conspiracy가 밟혀서 고민하느라 시간을 많이 썼다. 걍 닥치고 플랜디가 실력향상에 무조건 이득 + 플3 주변에도 충분히 재미있고 흥미로운 문제가 많음의 이유로 랭작은 접고 플랜디를 하도록 하죠. [P5] 다리 보수 공사(http:boj.kr/33319) 추천 ♥️: 흥미로운 DP. 선발고사는 선발고사다. 플5인데도 고민할 여지가 많네..[P3] 공주 구하기(http:boj.kr/2507) 추천 ♥️: bitonic tour DP라고 한다. 이런 이름은 살면서 들어본 적이 아예 없었는데, 지난 서울과기대 대회가 끝나고 cologne님이랑 떠들다가 이런 유형도 있다는 걸 알게 되었다. 옆에 계시던 ivori2011?님이 대표 문제로 공주 구하기가 있죠.. 라고..

지난 토요일(15일)에 프로그래머스 코드 챌린지 본선을 쳤다. 예선본선 선발 방식이 좀 독특했다.예선을 두 번에 나누어 진행했고, 총점과 총 소요 시간 합으로 등수를 매겨서 올린 것 같았다.첫 번째 예선 날은 MatKor Cup이 있었는데, 출제진이었지만 실례를 무릅쓰고 프로그래머스 다 친 다음에 대회장에 6시 딱 맞춰 가서 문제 해설을 했다.두 번째 예선 때는 피곤해서 반쯤 잠든 상태로 응시하는 바람에 브론즈 문제에 2시간씩 손댄 것 같았고.. 슬슬 뒤로 갈 수록 잠이 깼는데 결국 4번 문제 디버깅을 못해서 총점 715점이 나왔고, 못 올라갈 줄 알았건만 올려주더라.예선을 두 번에 나눠서 진행한 점은 좀 호감이었다. 특별한 이유는 아니고, 그냥 선발고사 시스템이랑 같길래 재밌어 보여서 ㅋㅋ.. 예선 문..

2월 8일[G1] Berry Picking(http:boj.kr/18319) 추천 ♥️: 굉장히 어려움. 내 체감은 P3이다.[P5] 시험(http:boj.kr/27654): 티피컬 평균값 최대화 파라메트릭2월 9일[G1] 햄최몇?(http:boj.kr/19645): 단순 반복문으로 구성된 DP라서 계산량이 좀 많아보여도 그냥 하면 됨. ICPC메타 ㅋㅋ2월 10일[R5] 수열의 합(http:boj.kr/33483): 내가 낸 문제. 별로 추천하진 않음 ㅋㅋ2월 11일[P5] Computer Network(http:boj.kr/10094) 추천 ♥️: 재밌는 문제. 지하철에서 친구(사실 형임)가 알려준 문제. 세 정거장 만에 풀었다.2월 12일[P2] Reachable Pairs(http:boj.kr/3..

며칠 또 게으르게 풀은 것 같다..근데 슬슬 P3 Queue에서 어려운/생소한 문제들만 남아가지고 더딘 것 같기도 하다. [P4] 국회(http:boj.kr/1226) 추천 ♥️: 새벽에 잠결에 PC방에서 켜고 찬우형 성준이형이랑 같이 잡았다. 의석 수 기준인데 그냥 정당 수 기준으로 봤나 그래서 왜 그리디가 아니냐라고 헛소리하다가 정신 차리고 냅색으로 풀어서 맞혔다.[P3] 수열의 개수 NKD(http:boj.kr/1336) 추천 ♥️: 디미고 정올반에서 20분 안에 풀어보라고 시켰다고 하길래 20분 걸고 시도했다. 20분 줬다길래 그냥 세그 DP인줄 알고 슥슥 했는데 문제를 잘못 읽었다. 다시 읽고 오래 걸려서 풀었다. 약간 코포틱한 DP인데 푸는 맛이 있었다.[P5] Arithmetic Progre..