반응형 2019/1031 [c++] 백준 #1162 도로포장 (190903) 다익스트라 알고리즘에 DP를 곁들인듯한 그런 문제이다. 무시 가능한 남은 도로의 개수를 dp로 계산해줘야 한다. dp[a][k]는 a까지 가는데 무시 가능한 도로의 남은 개수가 k개 있을 때를 의미하는데, 다익스트라에서 현재 edge를 무시한 cost를 dp[a][k-1]에, 합한 cost를 dp[a][k]에 넣어주면 된다. 그 이후 dp[N][0]~dp[N][K]까지 min값을 취하면 된다. 이 때 cost 값이 int형을 넘어갈 수 있으니 long long의 max값인 9223372036854775807 ? 이라는 값으로 INF를 바꿔주어야 한다. 직접 생각한 풀이는 아닌데 해보니까 생각보다 어렵지는 않았던 문제이다. #include using namespace std; .. 2019. 10. 8. [c++] 백준 #2957 이진 탐색 트리 (190906) map 연습문제이다. 삽입할 때마다 depth가 1증가하는데, 그만큼 counter가 증가한다는 사실을 이용해야 한다. key 값은 노드의 값, value는 depth 이런 식으로 map에 추가하면서 lower_bound를 사용해주면 된다. 약간 귀찮은 게 맨 첫번 째 원소 같이 앞에 값이 없는 경우. 예외처리만 잘 처리해주면 어렵지 않은 문제이다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back int main(){ ios::sync_with_stdio(false); cin.tie(0); int.. 2019. 10. 8. [c++] 백준 열혈강호 시리즈 with Network flow (190906) 열혈강호 https://www.acmicpc.net/problem/11375 열혈강호 2 https://www.acmicpc.net/problem/11376 열혈강호 3 https://www.acmicpc.net/problem/11377 열혈강호 4 https://www.acmicpc.net/problem/11378 열혈강호 5 https://www.acmicpc.net/problem/11408 열혈강호 6 https://www.acmicpc.net/problem/11409 Network flow 관련 시리즈 문제이다. 공부하면서 한번에 6문제를 거저먹는 나름의 꿀문제..?이다. 회사 직원이 있고, 일이 있고 한 회사 직원이 하나 혹은 그 이상의 일을 맡고, 하나의 일을 여러명이 맡는 것도 가능한 그런 .. 2019. 10. 8. [c++] 백준 내리갈굼 시리즈 with 세그먼트 트리 (190906) 내리 갈굼 https://www.acmicpc.net/problem/14267 내리 갈굼 2 https://www.acmicpc.net/problem/14268 내리 갈굼 3 https://www.acmicpc.net/problem/14287 내리 갈굼 4 https://www.acmicpc.net/problem/14288 세그먼트 트리 관련 문제이다. 1, 2는 세그먼트 트리를 곧바로 사용해도 되지만, 야자타임이 발생하는 3, 4번은 약간 응용 같은 느낌이다. 3번은 개별 update, 범위 find를 이용하면 된다. 4번은 개별 tree와 범위 tree 두 개를 동시에 쓰면 된다. 이 때 트리를 별도로 만들어야 한다. 왜냐하면 한 트리에서 야자타임했다가 안했다가 하면 구간합과 개별합이 엉망으로 합쳐지.. 2019. 10. 8. 이전 1 2 3 4 5 6 7 8 다음 반응형