넘치게 채우기

https://www.acmicpc.net/problem/3055BOJ - 탈출문제 유형: bfs, 그래프문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 ..

https://www.acmicpc.net/problem/16928BOJ - 뱀과 사다리 게임문제 유형: bfs, 그래프문제 난이도: Gold V시간 제한: 1초메모리 제한: 512초 문제뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 ..

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문제를..