문제 설명뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다.주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다.플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이..
문제 설명일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다.가희의 오른쪽에는 1번 건물이 있습니다.x가 1이상 N-1이하의 정수일 때, x번 건물의 오른쪽에는 x+1번 건물이 있습니다.N번 건물의 오른쪽에는 단비가 있습니다.가희와 단비가 볼 수 있는 건물은 아래와 같습니다.가희는 1번 건물을 볼 수 있습니다.k번 건물보다 왼쪽에 있는 건물들이 모두 k번 건물보다 높이가 낮다면, 가희는 k번 건물을 볼 수 있습니다.단비는 N번 건물을 볼 수 있습니다.k번 건물보다 오른쪽에 있는 건물들이 모두 k번 건물보다 높이가 낮다면, 단비는 k번 건물을 볼 수 있습니다.예를 들어, N..
문제 설명일직선으로 다양한 높이의 건물이 총 $N$개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다. $i$번째 건물 기준으로 $i - 1$, $i - 2$, ..., $1$번째 건물은 왼쪽에, $i + 1$, $i + 2$, ..., $N$번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.현재 있는 건물의 높이가 $L$이라고 가정하면 높이가 $L$보다 큰 곳의 건물만 볼 수 있다.바라보는 방향으로 높이가 $L$인 건물 뒤에 높이가 $L$이하인 건물이 있다면 가려져서 보이지 않는다.https://www.acmicpc.net/problem/22866 제한 사항 풀이문제를 요약하면, N개의 건물의 높이가 주어진다.특정 건물에서 볼..
문제 설명지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.불은 각 지점에서 네 방향으로 확산된다.지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.지훈이와 불은 벽이 있는 공간은 통과하지 못한다.https://www.acmicpc.net/problem/4179 제한 사항 풀이문제를 요약하면, 미로의 상태가 주어지고 J의 위치에서 시작하여 불을 피해 미로를 탈출할 수 있는지를 알아내야 한다.만약, 탈출할 수 있다면 최소 몇..
문제 설명N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는..
문제 설명길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라.https://www.acmicpc.net/problem/13144 제한 사항 풀이문제를 요약하면, N개의 수가 주어지면 연속한 수를 고를 때 유일한 수만 포함되도록 고르는 경우의 수를 구해야 한다. 해당 문제는 투포인터를 이용하면 간단하게 해결할 수 있다.시작점을 정하고 오른쪽으로 진행하면서 같은 수가 나오기 전까지 끝점을 옮긴다.만약, 같은 수가 나온다면 (끝점 - 시작점) 개만큼의 경우의 수를 추가할 수 있다.이후, 시작점을 오른쪽으로 한 칸 이동시킨다.그리고 위 과정을 계속 반복한다.끝점은 계속 유지하기 때문에 시작점을 ..
문제 설명상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.폭발은 다음과 같은 과정으로 진행된다.문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.https://www.acmicpc.net/problem/9935 제한 사항 ..
문제 설명도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2110 제한 사항 풀이문제를 요약하면, N개의 집이 주어지고 C개의 공유기를 설치해야 한다.C개를 최대한 넓은 간격으로 설..
문제 설명도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.https://www.acmicpc.net/problem/1863 제한 사항 풀이문제를 요약하면, 빌딩의 높이가 변경될 때 x, y좌표가 x의 오름차순으로 주어질때, 최소한의 빌딩의 개수를 구하는 것이다.문제를 글로만 읽으면 이해하기 어려울 수 있다.예시를 봐보자.101 12 25 16 38 111 015 217 ..
문제 설명1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.https://www.acmicpc.net/problem/7490 제한 사항 풀이문제를 요약하면, 1부터 N까지 연속한 수열의 사이에 연산자를 추가하여 0을 만들 수 있는 경우를 출력하는 것이다.이때, 연산자는 총 3개이다.+: 더하기-: 빼기' ': 이어 붙이기 해당 문제는 dfs(재귀)를 통해 해결할 수 있다.+와..
