문제가 쉬워보이는데, 정작 큐로 넣고 나면 다리에 이미 여러 차량이 있었을 경우의 time 측정에서 복잡해졌다. 사실 사고가 복잡하지... 그걸 정리하면 코드는 정말 쉬워진다는 느낌을 받았다. #include #include #include #include #include using namespace std; int solution(int bridge_length, int weight, vector truck_weights) { int answer = 0; int cur_count = 0; int cur_weight = 0; int index = 0; queue bridge; int truck = 0; while(true) { if(index == truck_weights.size()) { answer ..
[C++] 프린터
Priorities 에 있는 값을 pair로 만들어서 순서대로 queue에 push한다. [2,1,3,2] 의 경우, queue에 ,,, 이 순서로 push 시킨 것이다. 이후 priorities 내림차순으로 sort 한다. [3,2,2,1] 이 되는거임. 이게 곧 우선순위를 고려한 출력 순서가 될 것이다. 큐에서 비교의 대상이 된다. 비교하기 위해서 index = 0 값을 정의해둔다. 출력 페어의 순서를 저장하기 위해 queue result도 정의했다. 그리고 큐가 빌때까지 무한 루프를 돈다. 사이클마다 큐 내부 비교대상은 당연히 큐의 맨 앞값이다. 조건 1) 큐의 맨 앞의 우선순위 < priorities[index] 이 경우, 우선순위가 밀리는 것이기 때문에, 큐에 프론트 값을 푸쉬하고 큐를 팝한다...
[C++] 더 맵게
힙을 활용하는 문제긴 한데 힙이 하나도 기억 안나서 일단 내 방식으로 풀었다. #include #include #include #include using namespace std; bool cmp(int a, int b) { if(a == -1) return a > b; else if(b == -1) return a > b; else return a < b; } int solution(vector scoville, int K) { int answer = 0; sort(scoville.begin(),scoville.end(),cmp); while((scoville[0] < K || scoville[1] < K) && scoville[1] != -1) { scoville[1] = scoville[0] + s..
처음에 BFS 깊이 우선 탐색으로 풀려다가 막막해서 다른 사람의 풀이를 참고했다. https://ansohxxn.github.io/programmers/114/ [C++로 풀이] 게임 맵 최단거리 (BFS)⭐⭐ 📌 게임 맵 최단거리 ansohxxn.github.io 이분 참고함 1시간 투자해도 코드 완성이 안되면 그냥 바로 다른 코드 참고하는대신 복습하는 개인적인 룰이 있다.(변명변명) #include #include #include using namespace std; struct Pos{ int x; int y; Pos(int _x, int _y) { x = _x; y = _y; } }; int solution(vector maps) { const int N = maps.size(); const in..
[C++] 네트워크
나는 이런 벡터를 생성하고 값을 넣어줬다. vector network; for(int i = 0; i < computers.size(); i++) { vector net; for(int j = 0; j < computers.size(); j++) { if(computers[i][j] == 1) { //has edge net.push_back(j); } } network.push_back(make_pair(false,net)); net.clear(); } 3, [[1,1,0],[1,1,0],[0,0,1]], 2 (예제) 의 경우 bool vector false 0, 1 false 0, 1 false 2 bool값은 이 노드가 네트워크로 카운트되었는가를 저장할 것이고, vector는 이 노드에 연결된 모든 ..
이진 트리 탐색이 생소해서 처음부터 다른 사람 풀이를 참조했다. 문제 풀이는 https://velog.io/@euneun/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84C-BFSDFS 이분 걸 참조함. #include #include #include using namespace std; int answer = 0; void dfs(int sum, int depth, vector numbers, int target) { if(depth == numbers.size()) { if(sum == target) answer++; return; } dfs(sum+numbers[depth], depth..
처음에는 던전을 정렬하려고 했다. 던전당 최소 피로도 내림차순 -> 예제에서 털림 던전당 소모 피로도 오름차순(소모 피로도가 같다면 최소 피로도 내림차순) -> 예제에서 털림 모든 변수를 고려한 정렬의 방법이 있었을지 모르겠지만, 일단 나는 정렬로 풀기는 실패했다. 결국 모든 경우의 수 고려하기가 채택되었다. 이게 깊이우선탐색을 사용하면 될거란 생각은 들었는데, 아직 제대로 그쪽 공부를 안해서 되는대로 풀었다. 나는 next_permutation을 활용했음 다만 삽질을 좀 한게, 던전 당 최소 피로도가 같다면, 던전당 소요 피로도가 가장 작은얘 하나만 남겨둬도 된다고 생각했다는 점^^;; 그거때문에 케이스4에서 계속 오류가 났음. 이에 대한 반례는 감사하게도 질문하기에서 찾을 수 있었음! 40, [[40..
수리문제? 카펫의 가로길이:w 세로길이:h , 갈색타일의 수:b 노란색타일의 수:y 라고 두면 수식을 이렇게 짤 수 있다. B = 4+2(w-2)+2(h-2) Y = (w-2)(h-2) 여기서 미지수는 w, h니까 미지수 위주로 정리해보면 W+h = (b+4)/2 W*h = y+2(x+y)-4 이차방정식의 해로 구해도 되지만 가로 세로길이는 자연수이기 떄문에 하나씩 체크해도 괜찮다. 여기서, 세로길이가 가로길이보다 작거나 같다는 조건이 있기 때문에, 세로길이를 1로 두고, 세로가로의 합의 반보다 작거나 같을때까지만 반복문을 돌려서 체크해주면 된다. #include #include using namespace std; vector solution(int brown, int yellow) { vector a..
장르 이름 및, 장르에 속한 곡들의 재생수의 합으로 간단하게 맵을 만들어도 될 것 같다. 여기서는 정렬을 해야하니까 해시보다는 맵이 잘 어울리리라 생각했다. Index를 또 참고하기 싫어서 넣는김에 인덱스 값도 문자열로 변환해서 더해줬다. map genresMap; for(int i = 0; i < genres.size(); i++) { genresMap[genres[i]].first+=plays[i]; genresMap[genres[i]].second += to_string(i); } genre name : classic genre playtime : 1450 genre index : 023 genre name : pop genre playtime : 3100 genre index : 14 출력하면 이..