반응형 컴퓨터 사이언스65 [c++] 백준 #1561 놀이공원 (190822) 2019/10/08 - [분류 전체보기] - 백준 1939 중량제한 (8.22) 를 풀고 나서 이분 탐색을 어떻게 쓸지 고민하다가 일단 놀이기구의 총 운행시간을 0~max 설정한 후 이분탐색하면서 총 운행시간 안에 탑승하는 어린이들 수를 계산해보고 모든 어린이가 다 탈 수 있는 그런 운행시간을 계산해봤다. 그 이후 운행시간 – 1일 때 어린이 수를 구하고 운행시간을 1 더하고 나서 그 시간에서 나누어 떨어지는 놀이기구가 있으면 어린이 수를 더하고 그 수가 N이 되면 그 때의 인덱스가 마지막 아이가 타는 놀이기구이다. 마지막 아이가 타는 놀이기구를 타기 위해서 계산하는 부분은 내가 알아내진 못했지만 이분 탐색 접근 방법 자체는 잘한 것 같아서 칭찬하자~! 마지막 아이가 타는 놀이기구 = 주어진.. 2019. 10. 8. [c++] 백준 #1939 중량제한 (190822) bfs + 이분 탐색 문제이다. 0~w_max 사이의 중간 값으로 상한을 정한 후, bfs를 계속 돌면서 그 상한보다 더 큰 값의 edge만 지나갈 수 있게 한다. 그때 마지막 점에 도달가능한지 아닌지 확인해보면서 이 상한선을 estimate하면 된다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define MAX_N 100010 int N, M; vector graph[MAX_N]; bool visited[MAX_N]; int start, fin; bool bfs(int limit){ queue q; q.push(star.. 2019. 10. 8. [c++] 백준 #2011 암호코드 (190822) 초급 DP문제인데 재채점 되면서 틀린 걸 다시 풀어봤다. 다행히 다른 사람들 반례 + 내 코드 만으로 풀 수 있었다. 처리 해줘야 하는 경우의 수가 복잡해질 수 있지만 핵심은 다음과 같다. 1) 0으로 시작하면 무조건 0. 2) 0이 연속으로 두 번 이상 나오면 무조건 0 출력하기 3) i번째 인덱스가 0이 아니면 DP[i]에 DP[i-1]을 더해줌 4) I-1, I번째 인덱스가 합해서 10~26 사이의 값이면 DP[i-2]를 DP[i]에 더해줌 10달 전에 짠 코드를 봤는데 확실히 가독성도 훨씬 좋아지고 코드 자체도 많이 좋아졌다. 역시 연습이 답인 듯. 뭔가 감회가 새로웠다. #include using namespace std; #define INF 987654321 ty.. 2019. 10. 8. [c++] 백준 #2457 공주님의 정원 (190927) Greedy 방법. 회의실 배정과 비슷하게 풀면 된다. 3월 1일부터 11월 30일까지 매일 꽃이 하루에 한 개 이상 펴 있도록 꽃들을 선택할 때 선택한 꽃의 최소 개수를 출력해야 한다. 최소의 꽃을 선택하려면, 시작 시점이 증가하는 순서대로 정렬하고, 시작시점이 같으면 끝 지점이 작은 걸 위에 올린다. 정렬된 결과 예시는 다음과 같다. 1 1 5 31 1 1 6 30 5 15 8 31 6 10 12 10 시작 시간이 31(3월 1일)~1130(11월 30일)까지 갈 수 있다. 맨 처음에 끝 시간은 31로 초기화를 한다. 시작 시간이 제일 작은 애들부터 업데이트했기 때문에 맨 처음 애의 시작시간이 31보다 커버리면 아예 불가능하기 때문. 시작 시간이 현재 끝 시간보다 작은 애들을 탐색해보고,.. 2019. 10. 8. 이전 1 ··· 9 10 11 12 13 14 15 ··· 17 다음 반응형