Level 2. 마법의 엘리베이터 #include #include using namespace std; int solution(int storey) { if (storey < 10) return min(storey, 11 - storey); int left = storey % 10; return min(left + solution(storey / 10), 10 - left + solution(storey / 10 + 1)); }

Level 2. 배달 처음에 그냥 DFS로 해결하려다가 방문 여부를 관리하면서 최소 비용을 갱신하는 방법이 잘 떠오르지 않아 찾아봤다. 결국은 전형적인 다익스트라 알고리즘 문제였다.. [ 프로그래머스 배달 (Lv2) ] (C++) 프로그래머스의 배달(Lv2) 문제이다. [ 문제풀이 ] 1번마을에서 K시간내에 배달을 갈 수 있는 마을의 갯수를 구해야 하는 문제이다. #1. 구해야 하는 값 1번 마을에서 K시간내에 배달을 갈 수 있는 yabmoons.tistory.com vector를 활용한 인접 리스트로 그래프를 만들었다. 처음에 우선순위 큐에 시작점을 0의 비용으로 넣고, 매번 가장 비용이 적은 정점을 우선순위 큐에서 뽑는다. 뽑은 정점의 인접 정점들의 비용을 갱신한다. 인접 정점의 비용 > 나의 비용 ..

사용자 정의 자료형을 사용해 우선순위 큐를 사용할 때는 보통 아래와 같이 사용한다. 비교기 클래스를 선언하고, 크기를 비교하는 () 연산자를 오버로딩한다. priority_queue 형식으로 선언한다. #include #include using namespace std; struct Job { int start; int duration; }; class compare { public: bool operator () (const Job& A, const Job& B) { return A.duration > B.duration; } }; void main() { priority_queue prQue; prQue.emplace(Job {0, 4}); prQue.emplace(Job {1, 2}); prQue...

Level 2. 전력망을 둘로 나누기 2차원 vector를 활용한 인접 리스트로 그래프를 만들었고, 각 연결을 끊고 끊은 두 지점부터 DFS를 수행해 차이를 계산한 최솟값을 구하면 된다. #include #include #include #include using namespace std; int rDFS(vector& tree, int vertex) { int nConnected = 1; for (int j = 1; j < tree.size(); ++j) { if (tree[vertex][j]) { tree[vertex][j] = tree[j][vertex] = false, nConnected += rDFS(tree, j); } } return nConnected; } int calculate(vecto..

Level 2. 미로 탈출 최단 거리를 구해야 하는 전형적인 BFS 문제다. 출발지와 목적지의 거리를 구하는 함수를 만들어 재사용하면 편하고, 좌표에 unsigned 형을 사용하면 범위 검사가 간편해진다. #include #include #include using namespace std; struct Point { unsigned x; unsigned y; bool operator == (const Point& p) { return (x == p.x) && (y == p.y); } }; struct Entity { int level; Point point; }; int distance(vector& maps, Point from, Point to) { int X = maps.size(), Y = map..

Level 2. 메뉴 리뉴얼 코드가 다소 길긴 하지만 엄청 복잡하지는 않다. 모든 메뉴에서 가능한 n개 메뉴의 경우의 수를 구한다. 그 중 2번 이상 주문된 조합을 주문 수를 기준으로 메뉴 vector를 저장하는 set에 넣는다. 마지막에 가장 많게 주문된 조합들을 정답에 넣는다. 경우의 수 조합을 구할 때, 알파벳이 들어있는 map을 사용하므로 별도의 정렬은 필요하지 않다. 하지만, 모든 메뉴를 map에 넣어 가능한 경우의 수를 계산해서 그런지 시간 초과가 발생했다. // 이 풀이는 시간 초과가 발생한다. #include #include #include #include #include using namespace std; vector get_combinations(map& mp, int start, i..