Level 2. 광물 캐기 우선순위 큐를 활용한 문제인 줄 알았는데, 그냥 완전 탐색 문제였다. 최소 비용을 반환하는 DFS 재귀 함수를 만들고, 5개씩 각 곡괭이로 캐보고 가장 적은 비용인 경우를 반환하면 된다. #include #include #include #include #include using namespace std; int calculate(int pick, size_t from, vector& minerals) { static unordered_map cost[3] = { {{"diamond", 1}, {"iron", 1}, {"stone", 1}}, {{"diamond", 5}, {"iron", 1}, {"stone", 1}}, {{"diamond", 25}, {"iron", 5}, {..

Level 2. 혼자서 하는 틱택토 정답률이 낮은 다른 Level 2 문제에 비해 굉장히 쉬운 편이다. 보드 크기가 3 x 3 고정이 아니었다면, 적절한 난이도였을 텐데 고정이어서 쉽게 풀 수 있었다. 우선 O, X의 개수를 세어 (O - X) 가 0 혹은 1이 아니면 잘못된 판이다. 그리곤 승리한 경우를 확인해, O가 승리한 경우 X의 개수는 1 작고, X가 승리한 경우 O의 개수는 같다. 이 조건을 만족하지 못해도 잘못된 판이다. 마지막으로 O와 X가 모두 승리한 경우도 잘못된 판이다. #include #include using namespace std; int solution(vector board) { int nO = 0, nX = 0; for (string& s : board) for (char..

Level 2. 혼자 놀기의 달인 유니온-파인드의 Find를 응용해 해결할 수 있다. 상자를 열어 숫자를 확인해가는 과정이 유니온-파인드에서 대표 번호를 찾는 과정과 같기 때문이다. Find 과정에서 현재 집합에 속하는 숫자의 개수를 갱신하고, 다음 대표 번호를 찾기 전에 내 대표 번호를 자신으로 설정해주면 된다. 모든 수들이 하나의 집합에 속할 경우는, 두 번째 집합의 크기가 0임에 주의해야 한다. #include #include #include #include using namespace std; int findRep(vector& rep, int i, int& depth) { if (rep[i] == i) { depth = max(1, depth); return i; } ++depth; int ne..

Level 2. 3 x n 타일링 도저히 모르겠어서 어쩔 수 없이 보고 풀었다.. DP를 이용한 점화식 문제라는데, 1부터 대입해보며 규칙을 찾아 점화식을 만들어 해결하는 방법인 것 같다.. #include using namespace std; int solution(int n) { int DIV = 1'000'000'007; long pa = 1, a = 0, b = 0, c = 2; for (int i = 1; i < n; ++i) { long A = a, B = b; a = (c + pa) % DIV; b = c; c = (B + 2 * A) % DIV; pa = A; } return a; }

Level 2. 과제 진행하기 우선순위 큐와 스택을 적절히 활용하는 문제다. 우선순위 큐는 시작 시간을 기준으로 최소힙을 구성한다. 다음 시작 시간 전에 과제를 끝낼 수 있으면, 현재 과제를 끝낸 후 남은 시간동안 스택에 쌓아둔 과제를 수행한다. 과제 시간이 부족하면 할 수 있는 만큼만 하고 스택에 쌓아둔다. 마지막 과제이면 해결하고 루프를 빠져나온 후, 스택에 남아있는 과제를 차례로 끝내주면 된다. #include #include #include #include #include using namespace std; struct Plan { string name; int start; int playtime; Plan() : name(""), start(0), playtime(0) {} Plan(vecto..

Level 3. 파괴되지 않은 건물 당연히 시간 초과가 발생했다. // 이 풀이는 시간 초과가 발생한다. #include #include using namespace std; int solution(vector board, vector skill) { int answer = board.size() * board.front().size(); for (vector& sk : skill) { int r1 = sk[1], c1 = sk[2]; int r2 = sk[3], c2 = sk[4]; int degree = (sk[0] == 1) ? -sk[5] : sk[5]; for (int r = r1; r