반응형 전체 글82 [c++] 백준 #2613 숫자구슬 (190903) 최댓값이 N이하가 되도록 구슬을 나눌 수 있을까? 라는 질문으로 바꾸고 Binary search를 이용하면 된다. 이는 맨 앞에서부터 구슬을 하나씩 꽉꽉 채운다고 하면 한 번 search할 때마다 O(n)에 해결 가능하다. 최댓값을 기준으로 그룹을 나누면 m > M; for(int i=0; i> ball[i]; } int low = 0; int high = (N / M) * 100; //max value int mid; int ans = INF; while(low 2019. 10. 8. [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. 이전 1 ··· 8 9 10 11 12 13 14 ··· 21 다음 반응형