전체 글137 백준 g1 9328 열쇠 c++ https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 간단히 설명 input 맵에 벽, 대문자(자물쇠), 소문자(열쇠), $(먹어야 할 문서) 갖고 있는 열쇠 output 최대로 먹을 수 있는 문서의 개수 대문자 자물쇠는 소문자 열쇠로 열 수 있음 출발점은 건물 가장자리 아무데나 풀이 1. 갖고 있는 열쇠로 열 수 있는 곳은 모두 뚫어놓기 2. bfs로 건물 안 열쇠&문서 주워먹기 1~2를 반복한다. 다만 1) 새로운 열쇠를 먹었을 때만 && 새로운 공간이.. 2024. 1. 13. 백준 g1 16933 벽 부수고 이동하기 3 c++ https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 풀이 벽 부수고 이동하기 2(https://kyj0032.tistory.com/10)와 달라진 점은 낮과 밤이 생기고, 낮일 때만 벽을 부술 수 있다는 것이다. if 다음 위치가 벽이 아닐 때 평소처럼 bfs else if 다음 위치가 벽일 때 if 현재 시간이 낮이면 -> 벽 부수고 다음 위치로 이동 else if 현재 시간이 밤이면 -> 현재 위치에서 낮까지.. 2024. 1. 12. 백준 g3 14442 벽 부수고 이동하기 2 c++ https://www.acmicpc.net/problem/14442 런타임 에러는 함수가 int를 반환해야 하는데 아무것도 반환하지 않아서 생긴 에러 풀이 bfs를 돌릴 때, 자신이 부순 벽 개수랑 같이 이동한다. 이때 vis 배열을 2차원으로 두면 벽 부수고 이동한 거리 3 vs 벽 안 부수고 이동한 거리 5 둘 중 뭘 남길건지 애매해지기 때문에 dp처럼 모두 기록할 수 있도록 [n, m, 벽 부순 횟수] 3차원 배열로 둬야 한다. BFS 만약 다음 위치가 벽이 아니면, 그대로 BFS 다음 위치가 벽이면, vis[nx, ny, k+1]이 방문 되었는지 k+1가 K를 넘지 않는지 체크 후 기록 /*boj g3 14442 벽 부수고 이동하기 2*/ #include #include #include #defi.. 2024. 1. 12. 백준 g4 불 c++ https://www.acmicpc.net/problem/5427 풀이 1. 불이 퍼지는 시간을 나타내는 fireVis를 만든다. (BFS) 2. 상근이 위치를 BFS로 돌리면서 벽이거나, 불이 더 이전에 번진 곳이거나(상근이가 방문하는 시간보다 불이 퍼진 시간이 더 작을 때), 범위를 넘어가는 곳은 제외한다. 이때 불이 퍼진 시간이 0일 때는 불이 퍼지지 않았으면서 상근이가 방문하는 시간보다 작으므로, 예외처리 해주어야 한다. 고려한 것 1. 처음에는 불이 0초일 때 시작할 수 있으니 -1로 초기화하고 0부터 시작했으나 그냥 처음 시작을 1로 통일했다 /*boj g4 5427 불*/ #include #include #define MAXN 1005 using namespace std; int T, M, .. 2024. 1. 12. 백준 s1 1926 그림 c++ https://www.acmicpc.net/problem/1926 풀이 for (모든 좌표 i, j) if board가 1이고, vis 방문하지 않았다면 mx = max(mx, bfs로 나온 그림 크기) answer++; 실수했던 것 그림이 아무 것도 없을 때 max값이 0이 나와야 하는데 습관적으로 max = -1로 두어서 틀렸음 역시 틀린 게 있을 땐 문제를 다시 읽어보는 게 중요 /*boj s1 1926 그림*/ #include #include #define MAXN 502 using namespace std; int N, M; int board[MAXN][MAXN]; int vis[MAXN][MAXN]; int answer = 0; int mx = 0; int dx[4] = { -1, 0, 1, .. 2024. 1. 12. 백준 g5 5430 AC c++ https://www.acmicpc.net/problem/5430 풀이 배열을 뒤집을 필요 없이, 덱은 양 끝에서 pop이 자유로우므로 그 점을 사용해서 direction만 지정해주면 된다. 배열을 string으로 받을 때, 숫자가 두 자리수 이상이 될 때를 예외처리 해줘야 한다. /*boj g5 5430 AC*/ #include #include #include #define MAXN 100005 using namespace std; int T, N; string P; string arr; deque DQ; void strToDQ() { DQ.clear(); string str = ""; for (int i = 1; i < arr.size(); i++) { if (arr[i] == ']' || arr[i.. 2024. 1. 11. 백준 s4 1021 회전하는 큐 c++ https://www.acmicpc.net/problem/1021 deque 라이브러리 1. front에서도 삽입, 삭제가 O(1)에 가능 2. 벡터와 다르게 메모리상 연속된 위치에 존재하지는 않는다. 풀이 1. 찾아야 할 target의 위치를 찾는다. O(n) 2. 찾은 위치가 front와 가까운지, back과 가까운지 찾는다. 이때 back은 3번 연산의 수를 한번 더 해줘야 front에서 pop할 수 있으므로, if (log > N >> M; for (int i = 0; i > target[i]; for (int i = 1; i 2024. 1. 11. 백준 s4 2164 카드2 c++ https://www.acmicpc.net/problem/2164 /*boj s4 2164 카드2*/ #include #include using namespace std; int N; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N; queue Q; for (int i = 1; i 2024. 1. 10. 백준 g5 2493 탑 c++ https://www.acmicpc.net/problem/2493 풀이 역순으로 맨 뒤에서부터 시작 > N; for (int i = 1; i > tower[i]; } for (int i = N; i >= 1; i--) { int cur = tower[i]; while (!S.empty() && S.top().second < cur) { answer[S.top().first] = i; S.pop(); } S.push({i, cur}); } for (int i = 1; i 2024. 1. 10. 이전 1 ··· 12 13 14 15 16 다음
