Level 2. 2 x n 타일링 예제를 참고해 분석해보니 길이가 5일 경우, 5C0 + 4C1 + 3C2가 되는 것 같아서 구현해보았으나 틀렸다. // 이 풀이는 틀린 풀이다. #include #include using namespace std; int solution(int n) { int answer = 0; const int P = 1'000'000'007; vector factorials(n + 1, 1); for (int i = 2; i = j; --i, ++j) answer += factorials[i] / factorials[i - j] / factorials[j]; return answer; } 도저히 모르겠어서 힌트를 참고해보니 그냥 피보나치 수열과 모듈러 연산에 관한 문제였다고 한다...

Level 0. 등차수열의 특정한 항만 더하기 #include #include using namespace std; int solution(int a, int d, vector included) { int answer = 0; for (bool b : included) answer += (b ? a : 0), a += d; return answer; }

Level 2. 두 큐 합 같게 만들기 우선 앞뒤에서 추가/삭제가 빈번하므로 vector 대신 deque로 변환해 사용했다. vector를 그대로 사용하고 인덱스로 관리해도 되긴 하다. 두 큐의 차이를 관리하면서 0이 되는 시점을 찾았다. 두 큐의 차가 홀수라면, 합을 같게 만들 수 없으므로 바로 종료한다. 첫 번째 큐에서 n1만큼 두 번째로 옮기고 두 번째 큐에서 n2만큼 첫 번째 큐로 옮기면, 두 큐가 바뀌었을 뿐 0으로 만들 수 없다는 의미이므로 종료한다. 그럼 while 문의 조건이 diff && (cnt1 != n1 || cnt2 != n2)이어야 하는데 코드와 같은 이유는 아래 설명한다. 큐에서 원소를 옮기는 작업이 합을 기준으로 하기 때문에, 개수 조건 경계에서 한 큐에서 연속해서 2번의 p..

Level 0. 배열 만들기 3 #include #include using namespace std; vector solution(vector arr, vector intervals) { vector answer; for (vector& interval : intervals) answer.insert(answer.end(), &arr[interval[0]], &arr[++interval[1]]); return answer; }

Level 2. 문자열 압축 압축할 수 있는 모든 경우의 수를 찾아 실제 압축을 진행해 해결했다. 문자열의 길이가 4라면, 3개 단위부터는 압축이 불가능하므로 확인하지 않아도 된다. 벡터에 n 길이로 잘린 문자열들을 담은 후, 앞에서부터 동일한 문자열의 개수를 찾아 압축 문자열에 추가한다. 마지막 문자열 처리를 위해 쓰레기 값인 "0"을 추가해줬다. #include #include #include #include using namespace std; string compress(string& s, int n) { vector v; for (int pos = 0; pos < s.length(); pos += n) v.emplace_back(s.substr(pos, n)); v.emplace_back("0"..

Level 2. 124 나라의 숫자 십집수와 비교하며 패턴을 찾으면 된다. 124 나라에서는 십집수를 3으로 나눈 나머지가 0일 때 4, 4일 때 1, 2일 때 2가 된다. 124 나라에서 n자릿수로 바뀌는 십집수를 f(n)이라고 할 때, f(0) = 0 f(n) = 3ⁿ⁻¹ + f(n - 1) #include #include using namespace std; string solution(int n) { string answer; while (n) { int mod = n % 3; (n /= 3) -= (mod == 0); answer += "412"[mod]; } reverse(answer.begin(), answer.end()); return answer; }