알고리즘90 BOJ 1086 - 박성원 (dp, bit set) https://www.acmicpc.net/problem/1086 비트셋을 이용한 어려운 dp 수가 최대 15개 주어질 때, 이 수를 모두 사용한 순열을 순서대로 이어붙인 숫자 중 k(최대100)로 나눠떨어지는 것의 개수를 이용해서 확률을 구하라. dp[i][j] : i(집합) 골랐을 때 나머지가 j인 것의 수. 초기값은 0으로 한다. (단, dp[0][0] = 1) 최종적으로 dp[(1> k; for (int i = 0; i < n; i++) { for (int j = 0; j < len[i]; j++) { a[i] = a[i] * 10 + (num[i][j] - '0'); a[i] %= k; } } vector ten(51); //10의 i승의 k 모듈러값 ten[0] = 1; for (int i =.. 2020. 1. 5. Educational codeforces #69 div2 D - Yet Another Subarray Problem (dp) https://codeforces.com/contest/1197/problem/D 까다로운 dp문제 최대 3e5개의 숫자 배열이 주어진다. 연속된 부분수열 a[l..r]의 비용이 다음과 같을 때, 그 최대값을 구해라. (빈 부분수열의 비용은 0이다. 따라서 답의 최댓값은 0이다.) i번째에서 끝나는 연속된 부분수열은 다음 네 가지 경우로 나눌 수 있다. 첫번째 경우: 0 두번째 경우: a[i]-k 세번째 경우: 네번째 경우: psum(0,i)-k 이걸로 for문 디피하면된다. #include #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); using namespace st.. 2020. 1. 5. BOJ 1948 - 임계경로 (위상정렬) https://www.acmicpc.net/problem/1948 작업 https://suuntree.tistory.com/119문제의 응용 DAG(무사이클방향그래프)임이 보장됨. 시작점 ~ 도착점까지 최장거리를 구하고, 그 경로를 모두 칠했을 때 칠해진 간선의 수를 구하는 문제. 최장거리를 구하고 d배열 초기화 하는 것은 '작업' 문제와 동일함. 경로를 칠하는 것은 역방향 으로 정점을 순회하면서 d[next] = d[curr]+ weight(curr~next) 인 경우만 dfs로 따라가 주면 된다. 위 그림은 예제를 그대로 그린 것이다. 최장 경로는 12이므로, (7,2) 간선은 포함되지 않는다. 유의할 점은 이미 방문된 정점을 재 방문 하는 경우가 생긴다는 것이다. 위 예제에서 (7,2) 간선도 유효.. 2020. 1. 4. BOJ 2056 - 작업 (위상정렬) https://www.acmicpc.net/problem/2056 오랜만에 그래프문제 최대 10000개 작업들의 순서와 각 작업을 수행하는 데 걸리는 시간이 주어질 때 모든 작업이 끝나는데 걸리는 시간을 구해라. 예제의 상황을 그래프로 그리면 다음과 같다. 5번 작업을 수행하기 위해선 2번과 4번 작업이 모두 끝나야 한다. 1. i번까지 작업을 완료하는데 걸리는 시간을 d[i]라고 하고, 처음에 0으로 초기화 한다. 2. ind[i] == 0 인 정점들만 작업하는데 걸리는 시간으로 d를 초기화 한다. 3. 위상정렬된 순서대로 정점들을 방문하면서 d[next] = max(d[next], d[curr]+work[next])로 초기화해준다. 4. 위상정렬 후 d[i]중 최대값을 출력한다. #include #i.. 2020. 1. 4. 이전 1 ··· 4 5 6 7 8 9 10 ··· 23 다음
