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

Level 3. 길 찾기 게임 이진 트리를 구현하고, 좌표의 우선순위가 레벨 순회 순서로 되게끔 트리에 삽입한 후 전위 순회나 후위 순회를 하는 문제다. 좌표과 레벨 순회 순서가 되게 하려면, Y 좌표가 큰 것을 우선으로 하되 같은 경우 X 좌표가 작은 것을 선택하면 된다. 트리 구현을 정말 오랜만에 해보는데 학교 자료구조 시간에 워낙 실습을 많이 해서 그런지, 기어이 새록새록 떠올라 어렵지 않게 할 수 있었다. 삽입할 위치의 부모를 찾을 때는 X 좌표만 비교하면서 Up-down 형식으로 재귀적으로 찾으면 된다. 전위/중위/후위 순회 모두 재귀를 사용하면 쉽게 구현할 수 있다. #include #include #include using namespace std; struct Point { int id; ..

Level 3. 거스름돈 문제를 읽고 왠지 DP일 것 같은 느낌이 들었다. 이제 좀 감을 잡았나 보다.. 화폐 단위를 정렬하고 작은 화폐 단위부터 DP를 진행하는 이유는 중복을 처리하기 위함이다. [1, 2, 2]와 [2, 2, 1]은 같은 것이기 때문에 작은 것부터 수행해야 한다. for문에 금액이 먼저 오게되면, 중복 처리가 매우 번거로워진다. DP도 무작정 하는 것이 아니라, 중복을 고려해 때에 따라 정렬과 for문의 순서를 조정해야 한다. #include #include #include using namespace std; int solution(int n, vector money) { int DIV = 1'000'000'007; vector DP(n + 1, 0); DP[0] = 1; sort(..