반응형 2019/1031 [c++] 백준 #1987 알파벳 (190823) 완전탐색 문제. bfs 식으로 하면서 하면 되겠지? 하고? 코드를 짰는데 메모리 초과가 나왔다. 비트마스크도 써서 메모리 초과가 날 이유가 없는데 질문검색란에 나처럼 bfs식으로 푼 사람의 질문에 대한 답변을 보니 queue가 문제라고 한다. 뭔가 막연히 queue가 커지면 뻑가서 안된다는데 구체적으로 상상이 잘 안가서 직접 써봤다. (https://www.acmicpc.net/board/view/40634 에서 가져온 반례이다.) in: 20 20 ABCDEFGHIJKLMNOPQRST BCDEFGHIJKLMNOPQRSTU CDEFGHIJKLMNOPQRSTUV DEFGHIJKLMNOPQRSTUVW EFGHIJKLMNOPQRSTUVWX FGHIJKLMNOPQRSTUVWXY GHIJKLMNOPQ.. 2019. 10. 8. [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. 이전 1 ··· 4 5 6 7 8 다음 반응형