넘치게 채우기

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마리 상어들의 크기 정보를 모두 입수했다. 똑똑한 아기 상어 샼은 인천대학교 앞바다에 있는 상어들을 ..

https://www.acmicpc.net/problem/4042BOJ - Vampires!문제 유형: 구현문제 난이도: Silver I  문제The big media gimmick these days seems to be vampires. Vampire movies, vampire television shows, vampire books, vampire dolls, vampire cereal, vampire lipstick, vampire bunnies – kids and teenagers and even some adults spend lots of time and money on vampire-related stuff. Surprisingly, nowadays vampires are often th..

https://www.acmicpc.net/problem/2403BOJ - 게시판 구멍 가리기문제 유형: 기하학, 수학, 이진 탐색문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제교실 게시판에 압정을 사용하여 만들어진 구멍들을 안보이게 하기 위해서 두 개의 같은 크기의 정사각형 모양의 종이로 가리려고 한다. 두 종이는 서로 떨어져도 되고 서로 겹치는 부분이 있어도 상관없지만 모든 구멍들을 포함해야 한다. 단, 각 구멍은 크기가 매우 작아,  x, y 좌표로 표현되는 점으로 표현되고, 구멍이 종이의 경계나 모서리에 놓이는 것도 종이에 포함되는 것으로 한다.  게시판에 각 구멍의 위치가 주어지고, 두 종이가  모두 게시판의 틀에 대해서 수평과 수직으로 놓인다고 할 때,  모든 구멍을..