Little Jay

BFS를 기반으로 하는 문제이다. 단순히 BFS를 두번 돌리면 되는데, 첫 번째는 정상적인 BFS로, 두 번째는 R==G일때도 통과되게 만들면 된다. #include #define endl '\n' #define pii pair using namespace std; int t; int n; char graph[101][101]; bool visited[101][101]; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; int bfs(int x, int y, bool eye) { visited[x][y] = true; char target = graph[x][y]; queue q; q.push({ x, y }); while (!q.e..

문제를 잘 곱씹어보면 아이디어가 하나 떠올랐는데, 백준 문제의 '가장 긴 증가하는 부분 수열' 이 떠올랐다. 생각해보면 이 아이디어가 Correct하게 맞아떨어지는데, 이는 해당 구간에서 오름차순으로 증가하는 수열이 결국 이 문제의 상자와 같기 때문이다. #include #define endl '\n' using namespace std; int n; int dp[1001]; int arr[1001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i > arr[i]; } int ans = -1; for (int i = 1; i

사실 머리로 생각만 하면 간단한 문제인데 코드로 구현하려고 하니까 조금은 복잡한 문제였다. def solve(): A=[0, 0, 1, 8, 2, 2, 8, 9, 0, 3, 4, 0, 0] A.sort() i= A.count(0) if len(A) 2: count+=(A.pop()+A.pop())*i i*=10 count+=sum(A)*i return count

오랜만에 풀어본 Brute Force 문제 C++에는 순열을 쉽게 만들 수 있는 algorithm 헤더에 next_permutation(혹은 prev_permutation) 메서드가 존재한다. 그러나 우리가 풀고자 하는 것은 조합을 만들어야 하는 것이기 때문에 1의 개수를 L개 만큼, 그리고 0의 개수를 C-L개 만큼 넣어준다음에 해당 벡터에 1이 나온다면 출력하는 식으로 조합을 만들 수 있다. 그렇게 Possible한 String을 만들었다면 vowel과 noun의 개수가 맞는지 체크하고 출력해주면 되는 문제이다. #include #define endl '\n' using namespace std; int l, c; int main() { ios::sync_with_stdio(false); cin.ti..

간단한 bfs문제. https://euler.synap.co.kr/quiz=3 입력받아야 하는 수가 좀 많아서 그렇지 bfs만 돌리면 간단하게 풀 수 있는 문제였다. #include #define endl '\n' using namespace std; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; int display[1920][1080]; bool visited[1920][1080]; int bfs(int x, int y) { visited[x][y] = true; queue q; q.push({ x, y }); int size = 1; while (!q.empty()) { auto cur = q.front(); q.pop();..

코로나 확진 후 집에서 공부가 되지 않는 스타일이라 주구장창 놀기만 한 것 같다. 슬슬 블로그 운영 다시 해야겠다. 간단한 BFS문제였지만 오타때문에 맞왜틀을 1시간동안 하고 있던 문제다. 3차원 배열을 활용해서 벽을 부쉈으면 [][][1]쪽으로 이동해서 그쪽에서 부터 BFS를 돌리면 된다. 코딩 스타일이 cur.first.first 이렇게 전부 다 쓰는 스타일이라 여기서 까딱 실수해버리면 항상 맞왜틀 하고 있는 것 같다... #include #define endl '\n' #define pii pair using namespace std; int graph[1001][1001]; int visited[1001][1001][2]; int n, m; const int dx[] = { 1, -1, 0, 0 ..

요세푸스 문제가 단순히 Queue만 사용하는 문제라면 이 문제는 Deque를 이용하서 제거된 사람이 M과 일치하면 방향을 반대로 뒤집어서 요세푸스를 수행해야 하기 때문에 Deque 자료구조를 사용해야한다. 요세푸스 문제를 풀었다면 쉽게 해걀할 수 있었던 문제. #include using namespace std; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int n, k, m; deque dq; int counter = 0; cin >> n >> k >> m; bool flag = true; for (int i = 1; i

조금 짜증났던 구현문제 로마 숫자에 익숙하지 않아서 로마 숫자 개념을 이해하고 코드를 구현하는게 조금 어려웠다. Switch문을 사용할때 break를 안쓰게 되면 다음 Case로 넘어가기 때문에 이를 활용했다. #include #define endl '\n' using namespace std; string a; int t; int romanToNum(string& s) { int temp = 0; int aSize = s.size(); for (int i = 0; i < aSize; i++) { if (s[i] == 'M') { temp += 1000; } else if (s[i] == 'D') { temp += 500; } else if (s[i] == 'C') { if (s[i + 1] == 'M'..

피보나치를 이용한 재귀 문제였다. Zeckendorf's theorem을 사용하는 문제였는데, 이분의 블로그를 보면 쉽게 이해가 가능하다. 결과적으로 피보나치 수가 n 보다 클 때 직전항을 빼주면서 재귀적으로 내려가면 된다. #include using namespace std; long long fibo[10000001]; void solve(int n) { if (n == 0) return; for (int i = 0; i n; solve(n); cout

간단한 다익스트라를 활용한 웰노운 문제 크게 어려운 문제는 아니었지만 다익스트라가 무향그래프일때 동시에 그래프를 업데이트 하는 것을 잊지 말자. #include #define endl '\n' #define INF 987654321 #define pii pair using namespace std; int n, m; vector v[50001]; int dist[50001]; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 0; i > a >> b >> w; v[a].push_back({ w, b ..