넘치게 채우기

https://www.acmicpc.net/problem/1976BOJ - 여행 가자문제 유형: 플로이드 워셜, 유니온 파인드문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB문제동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.도시들의 개수와 도시들 간의 연결 여부가 주어져 ..

https://www.acmicpc.net/problem/16939BOJ - 2 x 2 x 2 큐브문제 유형: 구현, 시뮬레이션문제 난이도: Gold II시간 제한: 2초메모리 제한: 512MB 문제오늘은 2×2×2 루빅스 큐브를 풀어보려고 한다. 큐브의 각 면은 양방향으로 90도 돌릴 수 있게 만들어져 있다. 큐브의 각 면에 있는 색상이 모두 같으면 큐브를 풀었다고 한다.2×2×2 루빅스 큐브가 주어졌을 때, 정확히 한 번 돌려서 큐브를 풀 수 있는지 아닌지 구해보자. 입력첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. 출력루빅스 큐브를 정확히 한 번 돌려서 풀 수 있..

https://www.acmicpc.net/problem/23288BOJ - 주사위 굴리기 2문제 유형: 구현, bfs, 시뮬레이션, 그래프문제 난이도: Gold III시간 제한: 2초메모리 제한: 1024MB 문제크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는..

https://www.acmicpc.net/problem/14949BOJ - 외계 미생물문제 유형: 수학, 조합론, 정수론, 다이나믹 프로그래밍문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제항상 B, C가 가득 찬 성적표를 보고 자신이 컴퓨터 공학에 크게 재능이 없다고 생각한 윤영이는 결국 전공을 바꾸어 항공우주학과와 생물학과를 복수전공 하였고, 외계 생물 연구가로 큰 성공을 거두었다.그러던 중 어떤 행성에서 특이한 외계 미생물을 발견하게 되었고, 이를 신기하게 생각했던 윤영이는 몇 마리를 자신의 연구소로 가지고 왔다. 연구 결과 미생물은 다음과 같은 특징을 가지고 있음을 확인할 수 있었다.미생물은 스스로 자식을 낳으며, 하루동안 모든 자식을 낳고 죽는다. 낳을 수 있는 자식의 수..

https://www.acmicpc.net/problem/20119BOJ - 클레어와 물약문제 유형: DAG, 그래프, 위상 정렬문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제세상에는 N종류의 물약이 있고 클레어는 M개의 레시피를 알고있다.레시피는 (x1, x2, ..., xk) → r 형태로 표현할 수 있고 x1번, x2번 ..., xk번 물약을 모두 섞어서 r번 물약을 만들 수 있다는 뜻이다.현재 클레어에게는 y1번, y2번, ..., yL번 물약만 있다. 만들 수 있는 물약들을 전부 알아내주자.클레어가 가지고 있는 각 종류의 물약의 양은 무한대라고 가정하자. 입력첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시..

https://www.acmicpc.net/problem/2411BOJ - 아이템 먹기문제 유형: 다이나믹 프로그래밍문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제N×M 모양의 맵에 아이템과 장애물이 있다. 이때 맵의 왼쪽 아래에서 출발하여 오른쪽 위로 가려고 하는데, 중간에 모든 아이템을 먹으려고 한다. 이동할 때에는 오른쪽이나 위쪽으로만 이동할 수 있다. 또, 장애물이 있는 곳으로는 지날 수 없다.이때, 이동하는 경로의 개수가 총 몇 개인지 알아내는 프로그램을 작성하시오. 위의 예에서 ◎은 장애물, ☆는 아이템이다. 이때 경우의 수는 4 가지가 된다. 입력첫째 줄에 N, M(1 ≤ N, M ≤ 100), A(1 ≤ A), B(0 ≤ B)가 주어진다. A는 아이템의 개수이고, ..

https://www.acmicpc.net/problem/1922BOJ - 네트워크 연결문제 유형: MST(최소 신장 트리)문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 ..

https://www.acmicpc.net/problem/1111BOJ - IQ Test문제 유형: 수학, 구현, 조건분기, 브루트 포스문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB문제IQ Test의 문제 중에는 공통된 패턴을 찾는 문제가 있다. 수열이 주어졌을 때, 다음 수를 찾는 문제이다.예를 들어, 1, 2, 3, 4, 5가 주어졌다. 다음 수는 무엇인가? 당연히 답은 6이다. 약간 더 어려운 문제를 보면, 3, 6, 12, 24, 48이 주어졌을 때, 다음 수는 무엇인가? 역시 답은 96이다.이제 제일 어려운 문제를 보자.1, 4, 13, 40이 주어졌을 때, 다음 수는 무엇일까? 답은 121이다. 그 이유는 항상 다음 수는 앞 수*3+1이기 때문이다.은진이는 위의 3문제를..

https://www.acmicpc.net/problem/22238BOJ - 가희와 btd5문제 유형: 수학, 기하학, 정렬, 구현, 시뮬레이션문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제btd5에는 Darting Gun Tower가 있습니다. Darting Gun Tower는 아래의 알고리즘으로 풍선을 공격합니다.공격하고자 하는 목표물의 방향으로 공격 방향을 바꿉니다.공격 방향에 있는 풍선들의 체력을 d씩 낮춥니다.Darting Gun Tower는 좌표 (0, 0)에 하나 있습니다.Darting Gun Tower가 공격을 하게 되면, 공격하는 방향에 놓인 모든 풍선들은 동일한 수치의 피해를 입히게 됩니다.초기에 풍선은 N개 있고, Darting Gun Tower는 공격을 M번..

https://www.acmicpc.net/problem/19639BOJ - 배틀로얄문제 유형: 구현, 그리디문제 난이도: Gold V시간 제한: 1초메모리 제한: 1024MB 문제준석이는 총게임을 즐겨 한다. 준석이를 제외한 X명의 플레이어와 함께 게임을 하고 맵에는 Y개의 체력 회복 아이템이 떨어져 있다. 준석이는 처음에 체력을 M만큼 가지고 있다. 준석이는 아주 뛰어난 핵 프로그램을 사용하고 있어서 상대방을 보기만 하면 상대의 실력을 알 수 있고 싸웠을 때 자신의 체력이 어느 만큼 잃게 될지 정확히 맞힐 수 있다. 또 체력 회복 아이템이 어디에 있고 얼마만큼의 체력을 채워주는지 알 수 있다. 준석이가 이동하는 데 걸리는 시간은 무시하고 준석이를 제외한 X명끼리는 싸우지 않는다고 한다.준석이의 실력이..