안녕하세요~ 저는 모의고사 #4 풀이를 작성하게 된 신동원입니다. 백준 아이디 messi가 저예요!레프가 출제한 이번 모의고사 #4 9문제는 전부 Segment Tree를 이용해서 풀 수 있었습니다. A. 구간 합 구하기 수열 $A_1, ...., A_n$가 주어졌을 때, 원소 하나에 주어진 수를 더하는 쿼리와 $A_l, ...., A_r (1 \leq l \leq r \leq n)$의 합을 구하는 쿼리를 그 때 그 때 해결하는 문제입니다.세그먼트 트리를 이용해서, 세그먼트 트리의 각 노드가 관리하는 구간의 합을 저장해주면 쿼리당 $O(log(n))$만에 해결할 수 있습니다. B. 구간 합 구하기 2 수열 $A_1, ...., A_n$가 주어졌을 때, 주어진 구간의 모든 원소에 주어진 수를 더하는 쿼리와..

3회 모의고사는 DP-like 문제 8개로 만들었습니다.코드는 조금만 기다려주세요! A. 기차 여행 솔직히 이거 분류가 왜 DP인지 모르겠습니다. 그래도 좋은 문제라서 넣었어요. 문제의 핵심은 i번 열차를 몇 번 타게 되는지 카운트해주는 것입니다. Range-Update Fenwick / Segment Tree를 이용하면 간단히 \(O(n\lg n)\)에 해결할 수 있습니다. 다만 이 경우에는 쿼리(i번 열차를 몇 번 타는가?)에 대한 답을 online으로 구할 필요가 없고, 맨 마지막에 한 번만 구하면 된다는 특성을 이용하면 \(O(n)\) 복잡도에 해결할 수 있습니다. 배열 F[1..n]을 잡고,구간 [s,e)에 1을 더해주는 업데이트가 있다면F[s] += 1;F[e] -= 1;을 실행한 뒤맨 마지막..

코드는 잠시만 기다려주세요ㅠ A. 리조트 DP[i][j] 를 i일차를 살아내야 하는데 쿠폰이 j개인 상황에서의 최소 비용이라고 합시다.하루에 아무리 쿠폰을 득달같이 모아도 2개씩 모을 수 있으므로 j (i+1,j). 추가비용 0 i일에 수영이사 여행을 갈 수 있는 경우 : (i,j) -> (i+1,j). 추가비용 10000(i,j) -> (i+3,j+1) 추가비용 25000(i,j) -> (i+5,j+2) 추가비용 37000 (i,j) -> (i+1,j-3) 추가비용 0 (j >= 3) 단, 답은 DP[n+1][0] ~ DP[n+5][2*(n+5)] 중 최솟값임에 주의합시다. B. 카드 합체 놀이 허프만 알고리즘의 간단한 응용입니다. priority_queue를 이용해서 값이 가장 작은 두 카드 x, y..

코드는 Team github에서 압축파일로 받을 수 있습니다.압축 해제 비밀번호는 imeimi2000입니다. A. 소가 길을 건너간 이유 5 b[i]를 i번 신호등이 망가졌는가? 를 묻는 boolean 변수,S[i]를 ([i-K+1, i]의 신호등 중 망가진 것의 개수) = (b[i-K+1] + ... + b[i]) 라고 하면,문제는 min(S[K-1], ... , S[N-1]) 을 구하는 문제로 바뀝니다. S[i+1] = S[i] + b[i] - b[i-K]임을 이용하면 O(N)만에 문제를 해결할 수 있습니다. B. Binary Roads BFS를 정직하게 개조하면 해결할 수 있는 문제입니다. 정점 v를 (v,0)과 (v,1)의 독립된 2개의 정점으로 보고, 에지 u-v의 값이 0이면 (u,0) -> ..

트리 / 그래프의 기본기인 DFS technique를 연습하려고 한다.너무 쉬운 건 말고, Div.1 A ~ B 부터 짬짬이 풀어야지. 링크 396C. On Changing Tree 코드 트리에 기본적으로 DFS numbering을 해주자.잘 모르겠다면 코드, 또는 다음 설명을 참조. 노드 \(v\)가 발견되는 시점을 \(dt[v]\), 노드 \(v\)의 탐색이 끝나는 시점을 \(ft[v]\), 노드 \(v\)의 깊이를 \(dep[v]\)라고 한다.합 세그먼트 트리를 2개 관리한다. 각각 \(X, K\)라고 하자. type 1 쿼리 \((v,x,k)\) :\(X\)의 \([dt[v], ft[v]]\)에 \(x + k \cdot dep[v]\)를 더해줌.\(K\)의 \([dt[v], ft[v]]\)에 \(..

말그대로 여기서 태그에 DnC가 붙어 있는 놈들을 풀어보려는 시도입니다. 백준에서 좋은 DnC 찾기가 너무 힘들어서... 559B. Equivalent Strings 559B 문제가 말하는 "동치 관계"가 정말로 equivalent relation의 조건을 만족시킨다는 것이 관찰 포인트이다.그렇다면 한 string \(S\)의 대표원 \(r_{S}\)를 정해줄 수 있고, 편의상 사전 순으로 가장 빠른 string으로 정해주면 된다. 어떤 길이가 짝수인 string \(S = A + B\)에 대해서 \(r_{S} = \text{min}(r_{A} + r_{B}, r_{B} + r_{A})\)로 정해질 것이므로, 시간복잡도는 \(T(n) = 2T(\frac{n}{2}) + \) (문자열 비교하는 시간) \(..