본문 바로가기

cpp46

[개쉬운 풀이] 백준 3197 백조의 호수 CPP (21일차) https://www.acmicpc.net/problem/3197 문제 생각1. 먼저 호수의 영역을 숫자로 표현하여 구분한다.2. 물에 닿은 영역을 set을 활용하여 저장한다. (중복 방지)3. for문을 활용하여 set의 영역을 물로 만들고 다음 날 바뀔 영역들을 저장한다.4. 이때 백조들도 물 취급을 해준다.5. 백조들의 현재 영역을 비교하면서 반복한다. 어려웠던 점1. 영역을 처음에는 dfs를 통해 계속 숫자를 바꿔주려고 했지만, 시간초과에 직면하였다.2. 따라서 union find와 비슷하게 루트 영역을 만들어서 호수의 영역끼리 만나면 merge하였다.3. 백조도 물 취급을 해서 백조 위치의 영역도 생각해주어야 한다.4. melting()이 진행되기 전에, 다음 날 녹을 얼음들을 저장하면서 are.. 2024. 12. 13.
[개쉬운 풀이] 백준 12100 2048 (Easy) CPP (20일차) 문제 생각단순하게 구현 문제라고 생각했지만 구현하는 과정이 쉽지 않았다.처음 고려한 부분1. 좌 우 상 하 각각 구현하기2. 이때 board에 접근 방식에서 좌우, 상하에 따라서 row 부터 접근하는 지, col 부터 접근하는 지 다르다.3. space를 통해서 옮겼을 때의 빈칸의 위치를 찾으려고 했다.4. 합쳐졌을 때 같은 숫자인지 판별과 한번 합쳐진 숫자는 더이상 못합쳐지는 것을 중요하게 생각했다. 의외의 부분1. 숫자를 옮기는 과정에서 3중포문을 사용하고 싶지 않아서 2중포문을 사용하려고 했으나, 3중 포문을 통해 빈칸 처리를 해주어야 한다.2. 5번이 최대로 옮길 수 있는 경우다.3. row와 col을 접근하는 과정에서 은근 헷갈렸다.4. 혹시 몰라 long long으로 20x20을 대비했다. 풀.. 2024. 12. 12.
[개쉬운 풀이] 백준 13460 구슬 탈출2 CPP (19일차) 문제생각1. BFS를 통해서 구슬이 좌우상하로 가는 경우를 모두 확인하면 된다.2. 이때 구슬을 굴리면서 구슬이 같은 방향으로 굴러서 뭉치게 되는 경우를 조심해야한다.3. 따라서 구슬의 이동거리를 계산하여서 만약 같은 좌표로 모이는 경우 이동거리가 높은 구슬에게 한칸 뒤로 물리면 된다.4. 또한 10번 이하로 구슬들이 움직여야 한다. 풀이#include #include #include #include #include using namespace std;const int MAX = 11;struct P { int x, y, count, move; bool status; P(int x, int y, int c, int m, bool s) : x(x), y(y), count(c), move(m.. 2024. 12. 11.
[개쉬운 풀이] 백준 22866 탑 보기 CPP (18일차) 문제 생각1. 먼저 입력 갯수가 100000 이므로 이중 포문을 사용해서는 안 된다.2. 그래서 stack을 활용한 단일 포문으로 해결하였다.3. 왼쪽에서 오른쪽으로 stack을 통해서 건물 높이를 넣어주고, 스택 보다 더 낮은 높이가 나온다면 빼준다. 풀이#include #include #include using namespace std;int N;int Map[100001], Cnt[100001], Near[100001];stack> Stack, Stack_2;void input(){ cin >> N; for (int i = 1; i > Map[i];}// 왼쪽에서 오른쪽으로 탐색하며 더 높은 건물을 찾음void left_to_right() { for (int i = 1; i = 1; i--) .. 2024. 12. 9.

티스토리툴바