본문 바로가기

백준 문제 풀이

 (134)
백준 2805번 나무 자르기(C++) #include #include using namespace std; vector tree; int N, M; bool checkTree(int ch) { long long sum = 0; for (auto i : tree) { if (i - ch > 0) sum += i - ch; } if (sum >= M) return true; else return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin >> N >> M; int max = 0; for (int i = 0; i > tmp; tree.push_back(tmp); if (max < tm..
백준 7562 나이트의 이동(C++) #include #include #define MAX 301 using namespace std; int dX[] = { 2,-2, 1,-1, 2 , -1 , -2 , 1}; int dY[] = { 1,-1,2,-2, -1 , 2 , 1 , -2}; int dis[MAX][MAX] = { 0 ,}; bool visited[MAX][MAX] = { false, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int N; int Size; int nightX, nightY; int desX, desY; cin >> N; for (int i = 0; i > Size >>..
백준 1261번 알고스팟(C++) 벽을 부수고 이동한다는게 무슨 말인지 모를 수 있지만 결국 비용이 1인길을 선택하느냐 0인길을 선택하느냐의 차이이다. 우리는 목적지까지 최소한으로 이동해야하기 때문에 최대한 0인부분을 잘 이용해야한다. 그렇기 때문에 이 문제는 0-1 BFS 최소비용 or 다익스트라 문제이다. 처음에는 아래 코드로 했다가 예제에서 틀렸다. #include #include #include #define MAX 1001 using namespace std; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; deque Q; int dis[MAX][MAX]; int wall[MAX][MAX]; bool visited[MAX][MAX] = { false, }; void BFS(int N, i..
백준 13549 숨바꼭질3 (C++) 0-1 BFS, 다익스트라, 우선순위 큐 등 많은 방법으로 풀 수 있지만 한 번도 안해본 0-1 BFS를 사용해 풀어보았다. 이 문제의 출제 의도이자 최적화가 잘되어있어 0ms만에 문제를 풀어낼 수 있다. 0-1 BFS의 대한 알고리즘은 https://tigerfrom2.tistory.com/8 0-1 BFS 너비 우선 탐색 0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다. 0-1 bf tigerfrom2.tistory.com #include #include #include #define MAX 100001 using namespace std; int N, M; ..
백준 7576번 토마토(C++) 예전에 풀었던 문제이지만 다시한 번 해보았다. 예전의 코드는 구글링의 다른 사람의 코드를 도움 받았기 때문이다. 그리고 BFS의 좋은 예제이다. 먼저 토마토 1이 있으면 하루에 4방향으로 증식한다. 증식한 토마토는 또 4방향으로 증식하게된다. DFS로 계산하면 한 방향으로만 가버리기 때문에 적절하지 않다. 결국 BFS를 통해 첫 1부터 제일 떨어져 있는 거리까지의 최소거리(최소일수)를 구하는 문제로 귀결된다. 그러나 여기서 중요한 것은 1이 한군데만 존재하지 않는다는 것이다. 즉, 두군데 이상의 1에서 동시에 증식을 시작해야한다. 그림으로 표현하면 이런식이다. 때문에 DFS는 절대(적어도 내 기준에선) 사용할 수 없다. 알고리즘은 이러하다. 1. 처음 토마토가 심어져 있는 좌표를 큐에 삽입. 2. 삽입된..
백준 1966번 프린터 큐(C++) #include #include #include #include using namespace std; int S, N, M; int x; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> S; for (int i = 0; i > N >> M; int cnt = 0; for (int j = 0; j > x; Q.push(x); q.push(make_pair(j, x)); } while (!q.empty()) { int index = q.front().first; int value = q.front(..

티스토리툴바