본문 바로가기

백준34

BOJ 1176 - 섞기 (bit, dp) https://www.acmicpc.net/problem/1176 dp using bitfield중 기본문제. 최대 16명의 학생들의 키와 k값이 주어진다. 학생들을 일렬로 배치했을 때 모든 학생들의 인접한 학생과의 키 차이가 k이초과인 경우의 수를 구해라. f(s,t) : 현재 s, 마지막으로 배치된 인원이 t인 경우의 수 ans = f(0,n) -- (t==n인 경우 아무 인원이나 배치할 수 있다. [0base]) s==(1> a[i]; memset(dp, -1, sizeof(dp)); cout 2020. 1. 22.
BOJ 5670 - 새로운 자판 (Trie) https://www.acmicpc.net/problem/5670 이정도까진 풀수 있어야 한다. 자동완성 기능이 있는 자판이 있다. abczx abcxx abcyy 가 등록되어 있다고 가정할 때, a를 자판에 누르는 순간 abc가 자동완성된다. 등록되어있는 단어들을 모두 입력하는데 자판을 누르는 회수의 총합을 전체 등록된 문자의 수로 나눈 것을 구하자. 등록된 문자를 모두 find하면서 각 문자를 쓰는데 눌러야하는 자판 횟수를 ll cntKey(char* key, bool isRoot, ll cnt) 라고 하자. main에서 호출, 출력하는 코드 ll sum = 0; for (int i = 0; i cntKey(w[i], 1, 0); printf("%.2lf\n".. 2020. 1. 9.
BOJ 3176 - 도로 네트워크 (LCA) https://www.acmicpc.net/problem/3176 유독 LCA 코드를 짤 때 오타를 많이 내는것 같다. 최대크기 1e5인 간선 가중치가 있는 트리가 주어질 때, 1e5개의 쿼리에 답하는 문제. 쿼리 u, v : 정점u,v 사이의 경로 중 간선의 최소값과 최대값을 출력. u,v사이의 경로는 유일하다. 쿼리에 log(n)만에 답해야 한다. lca(u,v) 에서 u,v를 올려줄 때 그 과정을 따라가면서 간선 가중치 최소, 최대값(mn,mx)를 갱신할 것이기 때문에 depth를 이용하는 코드를 사용할 것이다. lca알고리즘을 다시 떠올려보자. u,v중 깊이가 더 깊은 정점을 u라고 강제하고, 1. u의 깊이를 v의 깊이에 맞춰 올려준다. 2. 같아진 u,v 깊이를 lca 직전까지 끌어올려준다. .. 2020. 1. 9.
BOJ 2228 - 구간나누기 (dp) https://www.acmicpc.net/problem/2228 최대 100자의 숫자배열을 입력 받았을 때 연속된 수열을 총 m개 뽑을 때 그 뽑힌 숫자들의 최대값을 구하는 문제. **dp값을 처음 초기화 할 때 특정 값으로 초기화 하기가 애매하다. 숫자가 음수일 수 있기 때문. 따라서 bool타입 c[101][51]을 사용해서 지금 상태가 이미 메모된 상태인지 기록해둔다. (psum 사용하므로 1-base ) f(i, j) : 1 ~ i 번째 숫자를 사용하여 j개의 연속된 수열을 뽑을 때 뽑힌 숫자들의 최댓값 f(i, j) = max(i번째 숫자를 뽑지 않을 때, i번째 숫자를 뽑을 때) 1. i번째 숫자를 뽑지 않는 경우 f(i,j) = f(i-1, j) 2. k번째 ~ i번째 숫자를 뽑는 경우 f.. 2019. 12. 29.

티스토리툴바