본문 바로가기
반응형

Problem Solving/BOJ228

백준 5397번 키로거 - C++ 풀이 1. 커서 앞쪽 문자와 뒤쪽 문자를 분리하여 각각 스택에 저장한다. 2. -가 들어오면 앞쪽 스택에서 pop 하고, 알파벳이 들어오면 앞쪽 스택에 push 한다. 3. >가 들어오면 뒤쪽 스택에서 하나를 pop 해 앞쪽 스택에 push 하고, 가 들어오면 뒤쪽 스택에서 하나를 pop 해 앞쪽 스택에 push 하고,가 들어오면 커서가 한 칸 뒤로 이동한다. 커서 바로 뒤에 있던 알파벳이 커서 앞으로 가는 것과 같다. 따라서 뒤쪽 스택에서 하나를 pop해 앞쪽 스택에 push 한다. > T; while (T--) { string s; cin >> s; cout 2022. 9. 8.
백준 2210번 숫자판 점프 - C++ 풀이 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 1. DFS를 사용하여 인접한 칸으로 5번 이동하는 모든 경우를 구한다. 5번 이동하므로 총 탐색해야 하는 상태 수는 25 * (4^5)로 매우 적기 때문에 브루트 포스로 해결할 수 있다. DFS를 통해 모든 경우를 구해서, 만들 수 있는 모든 수를 구해준다. #include #include using namespace std; int board[5][5]; unordered_set st; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; void DFS(int n, int r, int c, int curr) { if (n == 6) { st.insert(curr); return; } fo.. 2022. 9. 6.
백준 2607번 비슷한 단어 - C++ 풀이 1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다. 2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다. 3. 한 문자를 다른 문자로 바꾸면 같은 구성을 갖는 경우, 두 알파벳의 등장 횟수가 각각 -1, 1 씩 차이 난다. 1. 같은 구성을 갖는 경우, 모든 알파벳의 등장 횟수가 같다. 알파벳의 위치(순서)는 중요하지 않다. 각 알파벳의 등장 횟수만 같다면 같은 구성을 갖는다. 따라서 단어마다 각 알파벳의 등장 횟수를 세준다. A-Z까지 등장 횟수가 모두 일치한다면, 처음부터 같은 구성을 갖는 경우이다. 2. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, 한 알파벳만 등장 횟수가 1 차이 난다. 한 문자를 더하거나 빼면 같은 구성을 갖는 경우, .. 2022. 9. 5.
백준 4716번 풍선 - C++ 풀이 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. 1. DA와 DB의 차가 큰 순으로 풍선을 배부한다. A 풍선과 B 풍선의 합은 항상 K로 유지되어야 한다. 따라서 풍선이 모자라서 더 먼 곳을 택해야할 때 생기는 손해가 가장 큰 팀에게 먼저 풍선을 배부해서 손해를 줄여야 한다. 즉, | DA-DB | 값 내림차순으로 정렬한 뒤, 각 팀의 이동 거리가 최소가 되도록 배부해준다. #include #include #include using namespace std; typedef long long ll; struct Team { int k, da, db; }; int N, A, B; vector teams; bool cmp(const Team& lhs, const Team& rhs) { return ab.. 2022. 9. 3.
백준 2632번 피자판매 - C++ 풀이 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 2. A피자에서 연속된 조각을 선택하는 모든 경우에 대해 목표합을 만들기 위한 경우의 수를 더한다. 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 두 피자에서 연속된 조각을 선택하는 모든 경우를 고려하면 O(N^4)의 시간 복잡도가 소요된다. 따라서 두 피자를 각각 탐색한 뒤, A피자를 기준으로 대응하는 B 피자의 경우의 수를 구하는 방법을 사용하여 O(N^2)에 해결할 것이다. mp[i] = (B 피자에서 연속합이 i가 되도록 조각을 고르는 경우의 수)라고 하자. B 피자에서 연속된 조각을 선택하는 모든 경우에 대해 그 합을 구해 mp .. 2022. 9. 2.
반응형

티스토리툴바