1. 2048 (Easy)
1) 문제
문제 설명
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.입력
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.출력
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <iostream> #include <vector> #include <climits> #include <algorithm> using namespace std; int answer = 0; int N; vector<vector<int>> board; // 한 방향으로 보드를 이동 void moveBoard(int dir, vector<vector<int>>& inboard) { // 위 if (dir == 0) { for (int col = 0; col < N; col++) { vector<int> tmp; for (int row = 0; row < N; row++) { if (inboard[row][col] != 0) tmp.push_back(inboard[row][col]); inboard[row][col] = 0; } int idx = 0; for (int i = 0; i < tmp.size(); i++) { if (i + 1 < tmp.size() && tmp[i] == tmp[i + 1]) { inboard[idx++][col] = tmp[i] * 2; i++; } else { inboard[idx++][col] = tmp[i]; } } } } // 아래 else if (dir == 1) { for (int col = 0; col < N; col++) { vector<int> tmp; for (int row = N - 1; row >= 0; row--) { if (inboard[row][col] != 0) tmp.push_back(inboard[row][col]); inboard[row][col] = 0; } int idx = N - 1; for (int i = 0; i < tmp.size(); i++) { if (i + 1 < tmp.size() && tmp[i] == tmp[i + 1]) { inboard[idx--][col] = tmp[i] * 2; i++; } else { inboard[idx--][col] = tmp[i]; } } } } // 왼쪽 else if (dir == 2) { for (int row = 0; row < N; row++) { vector<int> tmp; for (int col = 0; col < N; col++) { if (inboard[row][col] != 0) tmp.push_back(inboard[row][col]); inboard[row][col] = 0; } int idx = 0; for (int i = 0; i < tmp.size(); i++) { if (i + 1 < tmp.size() && tmp[i] == tmp[i + 1]) { inboard[row][idx++] = tmp[i] * 2; i++; } else { inboard[row][idx++] = tmp[i]; } } } } // 오른쪽 else if (dir == 3) { for (int row = 0; row < N; row++) { vector<int> tmp; for (int col = N - 1; col >= 0; col--) { if (inboard[row][col] != 0) tmp.push_back(inboard[row][col]); inboard[row][col] = 0; } int idx = N - 1; for (int i = 0; i < tmp.size(); i++) { if (i + 1 < tmp.size() && tmp[i] == tmp[i + 1]) { inboard[row][idx--] = tmp[i] * 2; i++; } else { inboard[row][idx--] = tmp[i]; } } } } } void dfs(int depth, vector<vector<int>> inboard) { if (depth == 5) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { answer = max(answer, inboard[i][j]); } } return; } for (int dir = 0; dir < 4; dir++) { vector<vector<int>> copied = inboard; moveBoard(dir, copied); dfs(depth + 1, copied); } } int main() { cin >> N; board.resize(N, vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> board[i][j]; } } dfs(0, board); cout << answer << "\n"; return 0; }
2.. password-cracker
1) 문제
문제 설명
There are n users registered on a website CuteKittens.com. Each of them has a unique password represented by pass[1], pass[2], ..., pass[N]. As this a very lovely site, many people want to access those awesomely cute pics of the kittens. But the adamant admin does not want the site to be available to the general public, so only those people who have passwords can access it.Yu, being an awesome hacker finds a loophole in the password verification system. A string which is a concatenation of one or more passwords, in any order, is also accepted by the password verification system. Any password can appear or more times in that string. Given access to each of the passwords, and also have a string , determine whether this string be accepted by the password verification system of the website. If all of the string can be created by concatenating password strings, it is accepted. In this case, return the passwords in the order they must be concatenated, each separated by a single space on one line. If the password attempt will not be accepted, return 'WRONG PWASSWORD'.
2) 문제 분석 및 풀이
1) 설계, 분석
긴 문자열을 짧은 단어들로 분해 할 수 있는지 여부를 확인하는 문제
2) 풀이
unordered_map<int, bool> cache; vector<string> path; unordered_set<string> dict; string target; bool dfs(int idx) { if(idx == (int)target.size()) return true; //if (cache.count(idx)) return false; for (auto& word : dict) { if (target.substr(idx, word.size()) == word) { path.push_back(word); if (dfs(idx + word.size())) return true; path.pop_back(); } } //cache[idx] = false; return false; } string passwordCracker(vector<string> passwords, string loginAttempt) { dict.clear(); cache.clear(); path.clear(); target = loginAttempt; for (auto& pw : passwords) { dict.insert(pw); } if (dfs(0)) { string ans; for (int i=0; i < (int)path.size(); i++) { if (i >0) ans += " "; ans += path[i]; } return ans; } else { return "WRONG PASSWORD"; } }
