어제 올리려고 하다가 9시에 자버렸다 ㅁㄴㅇㄹ... 이번에는 MWT 특집.2011. 암호코드문제 : icpc.me/2011 간단한 dp인데, 0인 경우를 생각해주지 않으면 가버릴 수 있다. 입력 문자열을 \(S\)라고 하고, \(D[i]\)를 \(S_1 \cdots S_{i-1} \)를 해석할 수 있는 경우의 수라고 두자. 입력이 0으로 시작하지 않는다는 것이 보장되어 있으므로 \(D[2]=1\)이다. 이제 dp를 앞에서 뒤로 뿌려주자.\(S_i \neq 0\)인 경우, \(S_i\)를 하나의 암호문으로 해석할 수 있으므로 \(D[i+1]+=D[i]\).\(S_i \neq 0 \wedge 10S_i + S_{i+1} < 27\)인 경우, \(S_iS_{i+1}\)를 하나의 암호문으로 해석할 수 있으므로 ..

#1. 중량제한 문제 : icpc.me/1939 굉장히 다양한 풀이가 가능한 문제인데, description을 잘못 이해해서 ㅂㄷㅂㄷ하다가 결국 풀이를 까봤다. 1. BFS 물건을 보내는 공장을 \(s\), 받는 공장을 \(t\)라고 하자.또 각각의 정점까지 수송할 수 있는 최대의 비용을 \(F[v]\)라고 하자.(정점 \(v\), c=\(s\)에서 \(v\)까지 옮길 수 있는 최대 비용)의 순서쌍을 저장할 수 있는 큐 \(Q\)를 잡고, \(Q\)에 \((s,F[s]\leftarrow \infty)\)를 넣으면서 BFS 개시. \(Q\)가 빌 때까지, \(Q\)의 front \(k\)에 대해서 \(k.v\)에 연결되어 있는 점 \(u\)들을 보는데, \(min(k.c,bridge\_capacity[v\..

1. 이상한 수열 (OJUZ #10) http://icpc.me/11917 http://oj.uz/problem/view/OJUZ10_bizarre 풀이 : oj.uz에서 처음 봤을 때 아무 생각 없이 62점을 받고 넘겼던 문제다. 100점 풀이 생각 못한 뚝배기를 매우 쳐라 \(M\)이 비상식적으로 크므로, \(B_i\)의 값을 거의 닫힌 꼴로 구할 수 있을 것이라는 생각을 해야 한다. \(S\)를 오름차순으로 정렬한 뒤, \(B_{n+1}\)의 값 (\(S_1, S_2, \cdots S_n\) 중 서로 다른 수의 개수)이 어떤 \((S_i,S_{i+1}]\)에 있게 되면 이 값은 \(S_{i+1}\)로 수렴하고(편의상 \(S_{n+1} = \infty\)라 두자), 그 전까지는 값이 1씩 증가하게 됨..

*이 문제 set은 백준 온라인 저지에서 랜덤을 돌려서 푼 문제들입니다. 풀이를 좀 포멀하게 적고 싶어서 쉬운 문제라도 모두 풀이를 상세하게 기록할 예정이니, 그게 마음에 들지 않으신 갓갓분들은 살포시 뒤로가기를 눌러 주세요. 1. 수열 축소 문제 : http://icpc.me/2237 풀이 : 얘는 고1때 정올을 딱 시작할 때쯤 풀지 못하고 넘겨버린 문제. 사실 CON이란 연산이 전혀 대단하지 않다는 것만 알면 된다. CON연산을 수행한 결과는 수열의 인접한 원소 사이에 + 또는 -의 부호를 적절히 삽입하여 계산한 식이다. (단, \(a_2\)앞에는 반드시 -가 붙는다) 그래서 \(n \times (2\sum{a_{i}}+1)\) dp table을 잡고,\(dp(i,j) : a_{1}~a_{i}\)까지..

문제 보기http://acmicpc.net/problem/10847http://oj.uz/problem/view/APIO15_skyscraper 1. Problem Statement \(N\) 개의 건물 위에 \(M\)마리의 도게가 있는데, 각 도게는 한 번의 움직임으로 정확히 \(p_{0},p_{1},...p_{M-1}\)만큼 이동할 수 있다.이 때 건물 \(s\)에서 시작해서 \(e\)로 릴레이하면서 갈 때, 점프의 최소 횟수를 알고 싶다. 2. Subtask2 - 36점 (\(N,M \le 2,000\)) Subtask1은 백트래킹이다. 짠 적도 없고, 설명하기 까다로운 만큼 넘어가자. 기본적으로 이 문제의 풀이는 다익스트라 알고리즘이다.겨울학교에서 이 문제랑 비슷하게 생긴 문제를 못 푼 기억이 있..