넘치게 채우기

https://www.acmicpc.net/problem/16964BOJ - DFS 스페셜 저지문제 유형: DFS/BFS문제 난이도: Gold III시간 제한: 2초메모리 제한: 512MB 문제BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.void dfs(int x) { if (check[x] == true) { return; } check[x] = true; // x를 방문 ..

https://www.acmicpc.net/problem/14501BOJ - 퇴사문제 유형: 다이나믹 프로그래밍문제 난이도: Silver III시간 제한: 2초메모리 제한: 512MB 문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자.일자1일2일3일4일5일6일7일T_i3511242P_i1020102015402001일에 잡혀있는 ..

https://www.acmicpc.net/problem/3485BOJ - Play on Words문제 유형: 그래프 이론, 오일러 경로, 오일러 회로, dfs문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.There is a large number of magnetic plates on every doo..

https://www.acmicpc.net/problem/1629BOJ - 곱셈문제 유형: 수학, 재귀, 분할 정복문제 난이도: Silver I시간 제한: 0.5초메모리 제한: 128MB 문제자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 풀이거듭제곱의 끝자리수 사이클을 이용하는 방법은 느리다.대신, 분할 정복을 이용하여 문제를 풀 수 있다.따로 dp테이블같은거에 저장할 필요는 없다.한 번 이외에 추가적인 인출 및 ..

https://www.acmicpc.net/problem/2206BOJ - 벽 부수고 이동하기문제 유형: bfs, 최단거리문제 난이도: Gold III시간 제한: 2초메모리 제한: 192MB 문제N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한..

https://www.acmicpc.net/problem/1931BOJ - 회의실 배정문제 유형: 정렬, 그리디문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB  문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주..

https://www.acmicpc.net/problem/1753BOJ - 최단경로문제 유형: 최단거리, 다익스트라, 우선순위 큐문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는..

https://www.acmicpc.net/problem/1261BOJ - 알고스팟문제 유형: bfs, 다익스트라, 최단 경로문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), ..

https://www.acmicpc.net/problem/6907BOJ - Floor Plan문제 유형: BFS, DFS, 그래프, 정렬문제 난이도: Silver I시간 제한: 1초메모리 제한: 128MB 문제The floor plan of a house shows rooms separated by walls. This floor plan can be transferred to a grid using the character I for walls and . for room space. Doorways are not shown. Each I or . character occupies one square metre.In this diagram, there are six rooms.You have been g..

https://www.acmicpc.net/problem/30892BOJ - 상어 키우기문제 유형: 스택, 그리디문제 난이도: Silver I시간 제한: 1.5초메모리 제한: 1024MB 문제인천대학교의 앞바다에는 N마리의 상어가 살고 있다고 한다. 각각의 상어는 서로 같거나 다른 크기의 몸집 A_i를 가지고 있다. 상어의 세계는 완전한 약육강식의 세계로, 상어 자신의 크기보다 작은 상어는 전부 먹을 수 있다. 이때, 상어의 크기는 잡아먹힌 상어의 크기만큼 커지게 된다. 반면, 자신의 크기 이상인 상어는 전혀 잡아먹지 못한다.어느 날 크기가 T인 샼이라는 이름의 아기 상어는 인천대학교 앞바다에 존재하는 N마리 상어들의 크기 정보를 모두 입수했다. 똑똑한 아기 상어 샼은 인천대학교 앞바다에 있는 상어들을 ..