지문이 짧길래 저번에 카페에서 떠들다가 핸드폰 메모장을 이용해서 대충 풀이를 내봤는데 흥미로웠다.어제 메모장 정리하다 메모를 발견해서 구현해보았다. 일단 문제 자체가 너무 점화식으로 잘 표현될 수 있을 거라는 느낌을 풍긴다.이 문제의 어려움은 $n+1$개의 직사각형 중 $n$개는 정확히 계단 모서리에 하나씩 걸치지만 딱 한 개의 직사각형은 중앙 어디에든 위치할 수 있다는 점에 있다. 따라서 중앙 어디에든 위치할 수 있는 직사각형의 위치를 고정시킨다면 문제가 수월해질 것이다. 고정했다고 생각하고 문제를 바라보면, 직사각형의 두 변을 연장해서 가능한 답의 꼴들을 찾아볼 수 있다.무조건 두 변 중에 한 변의 연장선은 어떤 조각도 가로지르지 않는다는 관찰이 핵심적이다. 이를 이용하여 약간의 포함배제를 적용하면 ..
https://mathsciforstudent.tistory.com/390 그새 또 잔뜩 만들어 왔다. 2월에 비해 새로 추가된 문제는 [지워진 ETT], [코드마스터 2024], [찬물 샤워], [코드마스터, 슬라이딩 퍼즐 마스터, 보드게임 마스터], [물탱크 알바(Hard)], [Simple Tree Decomposition Problem]이 있다. [지워진 ETT]는 SUAPC 2024s에 출제한 문제로, 아마 문제 구상은 [Sieve Game] ~ [신촌방위본부: 지하 벙커의 비밀]과 비슷한 시기에 했던 것 같다. 아마 KAIST 2023 Mock Competition의 Call for Tasks에 넣어서 떨어졌나 그랬을 것이다. azberjibiou님과 songc님만이 검토하였고 당연히 이 내용..
오랜만의 문제 풀이이다.KSAAC 2023 summer에 출제된 테마파크 문제이다. $s$의 서브트리를 기준으로, 어떤 두 간선도 조상-후손 관계에 있지 않은 간선 집합들을 관리해두면, $s$와 부모를 잇는 간선과 비교해서 써먹을 수 있을 것 같다. $s$와 부모를 잇는 간선에서의 비용을 $w_s$라고 하자. 당연히 $s\ge 1$일 때만 정의할 수 있다. 서브트리 속 여러 정보를 효율적으로 관리하는 것은 보통 스몰투라지 기법이 잘 먹힌다. 풀이를 조금 더 구체화해보자. 우선, 각 정점은 자신보다 윗쪽에 있는 간선들과 교류가 생기므로 일반적으로 트리 문제를 풀 때 $s$의 서브트리에 정점 $s$를 포함하는 것과는 달리, 정점 $s$는 제거하는 식으로 값들을 정의하자. $\ell_s:=$ 정점 집합 $s^..
안녕하세요, 블로그 주인 김도훈입니다! 제가 고등학교 3학년 때 끙끙대며 만든 중고등학생 대상 대회가 올해에도 2회 차로서 이어서 열리게 되었습니다! 올해도 제가 대회 전반에 걸쳐 작년의 퀄리티를 유지하려고 열심히 노력하고 있으니… 많은 관심 부탁드립니다! 전국 중고등학생 대상으로 오프라인 대회, 코드마스터 2024가 열립니다! 대회는 8월 31일, 송도고등학교에서 진행됩니다. https://boj.kr/songdo2023에서 작년 문제들을 확인하실 수 있고, 작년과 비슷한 구성으로 출제될 예정입니다.자세한 내용은 포스터와 QR 코드 [신청 링크]를 통해 확인하실 수 있습니다. 대회에 관한 여러 최신 정보를 인스타 @code_master2024 에 공지할 예정이니 참고해주세요. 감사합니다.
code-challenge.elice.io Day 6 문제는 밤 11시 30분 정도에 접속해서 본 다음 열심히 고민했는데 풀지 못했고.. 적당한 전략으로 60점 정도의 부분 점수를 긁었습니다. Day 7부터는 긴장을 늦추지 말고 일찍 확인해야겠습니다! 엘리스 코드 챌린지 Day 7에는 '계기판 조작하기'라는 문제가 나왔습니다.Day 7 문제를 보고 저는 우선 digit DP를 떠올려 보았습니다. 하지만 digit DP를 짜는 것이 번거롭기 때문에, 다른 방법이 있는지 좀 더 고민해보았습니다.그런데 그냥 näive한 방법이 통과할 것 같아서 그렇게 풀어 맞췄습니다. 방법은 그냥 '자연수 $i$의 모든 자릿수의 종류가 정확히 $K$일 때까지 $i$를 늘리며 반복'입니다.최악의 경우는 $N=10^7$인 경우인..
code-challenge.elice.io사진을 못 찍었습니다.원소 $N$개의 $2^N$가지 모든 부분수열의 합들이 주어졌을 때, 원래 원소 $N$개를 오름차순으로 구해서 출력하면 되는 문제였습니다. 10시 알람에 깨서 비몽사몽 풀었더니 여러번의 오답을 누적했네요..ㅠㅠ 모든 원소가 음이 아닌 정수이기 때문에 "$a_1,\cdots,a_{i-1}$로 구성할 수 있는 모든 합"을 $\{s\}$에서 반복적으로 덜어내면 됩니다. 모두 덜어내졌다면 $\{s\}$에 남은 가장 작은 값은 $a_i$가 됩니다.이로써 새로운 원소를 추론하였기에, 다시 "$a_1,\cdots,a_{i}$로 구성할 수 있는 모든 합"을 모두 덜어내면 다음 과정으로 진행할 수 있습니다.#include using namespace std;m..
code-challenge.elice.io 엘리스 코드 챌린지 Day 4에는 '트리 위의 게임'이라는 문제가 나왔습니다.Day 3처럼, 알고리즘 문제를 평소에 풀어보지 않은 사람들에게는 다소 어려울 수 있는 난이도로 나왔습니다. 저는 오늘부터 알람을 10시에 맞춰두고 풀기로 했습니다. $\mathrm{dfs}(s,\cdot)$이 $s$에서 게임을 시작했을 때 얻을 수 있는 점수라고 정의합시다. 게임에서 가능한 수들이 공개되어 있고, 사람에 따라 가능한 게임 속 시행에 차별이 없다면 보통, 게임은 사이클이 없는 방향 그래프(DAG; directed acyclic graph)로 모델링 되며, 각 게임의 상태는 정점 하나로 표현되고 정점은 승리 또는 패배의 상태를 갖게 됩니다. 어떤 상태에서 진행할 수 있는 ..
code-challenge.elice.io 엘리스 코드 챌린지 Day 3에는 '문자열 압축 해제'라는 문제가 나왔습니다.Day 1, 2에 비해 갑자기 어려워져서 놀랐습니다. 괄호가 포함된 문자열을 해석할 때는 스택(stack) 자료구조와 재귀적인 접근을 이용하는 것이 좋습니다. 문제를 풀기 전, 괄호 문자열에 대해 여는 괄호는 닫는 괄호 짝의 인덱스를, 닫는 괄호는 여는 괄호 짝의 인덱스를 빠르게 찾을 수 있도록 스택을 이용하여 opened[N], closed[N] 배열에 기록해둡시다. 문제를 해결하기 위해 문자열 $S$에 대해 $\mathrm{solve}(S)$를 정의합시다.이때, 문자열 $S$는:첫 번째 문자가 숫자여야 하고,괄호로 이루어진 부분수열(subsequence)이 올바른 괄호 문자열을 이룬..
code-challenge.elice.io 엘리스 코드 챌린지 Day 2에는 '정리 정돈을 좋아하는 k씨'라는 문제가 나왔습니다. 저는 다음과 같이 copy, sort 함수를 이용하여 단순하게 코드를 작성했습니다.#include using namespace std;const int N = 10003, M = 503;int n, m;int a[N], b[N];int main() { cin >> n >> m; for(int i=1; i> a[i]; while(m--) { int i, j, k; cin >> i >> j >> k; copy(a+i,a+j+1,b+i); sort(b+i,b+j+1); cout
