(17.11.23 시작)푼 거라곤 D 하나지만... (그것마저도 솔루션 까봄) 앞으로 업데이트됩니다. BOJ 번호는 3405 ~ 3415. A. Kingdoms B. Who wants to live forever? C. Chemist's vow Tag : Implementation, Dynamic Programming http://icpc.me/3408 주기율표 원소들을 웹에서 긁어서 스트링 배열에 저장한다. 한 글자 원소는 14개, 나머지 원소는 100개가 나온다. (2016년에 추가된 Nh, Mc, Ts, Og는 사용하면 안된다!) 입력 문자열을 \(S\)라고 두고,\(dp[x][i]\)를 \(x\)글자짜리 원소를 사용해서 \(S_{1}\cdots S_{i}\)를 만들 수 있는가? 와 같은 boole..

BOJ 링크 내가 아는 풀이만 3개다. 3개 다 멋진 풀이라서 공유하기로 한다. 3개 풀이 모두 다익스트라 전처리가 필요하다. 대신 시작 정점이 축제가 열리는 K개의 정점 모두다! 다익스트라는 시작 정점이 꼭 하나일 필요가 없다. 납득이 가지 않는다면 시작 정점들을 모두 하나의 큰 정점으로 연결한다고 생각해 보자. 시작 정점이 1개인 다익스트라로 바뀐다. 구현도 간단하다. 맨 처음 heap에 (cost = 0, vertex = 시작 정점)을 넣을 때 K개를 다 넣고 일반적인 다익스트라를 돌리면 된다. 이 과정이 끝나면 모든 정점 \(v\)에 대해 축제가 열리는 정점까지의 최단거리인 \(d[v]\)를 얻는다. 이제 쿼리를 오프라인으로 처리할 건데, 처리 방법이 3개의 풀이에서 모두 조금씩 다르다. 1. S..

안녕하세요 탐렢입니다!5번째 모의고사에는 std::set, std::map 등의 자료구조를 익히기 좋은 문제들을 모아놓았습니다.맞은 뒤에도 적극적으로 저나 다른 멘토들의 코드를 보면서 STL 활용법을 얻어가세요! A. 숫자 카드 2 map을 이용해서 해결할 수 있는 간단한 문제입니다. 좌표압축을 해도 되지만 map이 훨씬 간단하죠! map M;X가 적힌 숫자 카드 저장 : ++M[x]; X가 적힌 숫자 카드의 개수 출력 : cout S; 사원 넣기//마지막 글자가 'r'인지만 체크하면 된다.if(X.back() == 'r') S.insert( X.substr(0, X.size() - 6) ); // " enter"를 제외한 사원명을 X에 삽입else S.erase( X.substr(0, X.size() ..

안녕하세요~ 저는 모의고사 #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..