전체 글

문제 설명길이가 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개를 최대한 넓은 간격으로 설..

문제 설명세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1$1$행 1$1$열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.https://www.acmicpc.net/problem/1987      제한 사항      풀이문제를 요약하면, R x C 문자로 이루어진 2차원 행렬이 주어지면, ..

문제 설명젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야..

문제 설명도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.https://www.acmicpc.net/problem/1863      제한 사항      풀이문제를 요약하면, 빌딩의 높이가 변경될 때 x, y좌표가 x의 오름차순으로 주어질때, 최소한의 빌딩의 개수를 구하는 것이다.문제를 글로만 읽으면 이해하기 어려울 수 있다.예시를 봐보자.101 12 25 16 38 111 015 217 ..

문제 설명N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2138      제한 사항      풀이문제를 요약하면, 시작상태에서 스위치를 켜 최종상태로 만들 때, 최소한의 스위치를 켜는 횟수를 구하는 것이다.스위치를 키면, 왼쪽, 가운데, 오른쪽 스위치가 변한다.만약, 끝쪽(0 혹은 N) 일 경우엔 무시한다. 문제의 접근법은 그리디를 이용해 최적의 상태를 만들어 나가는 것이다.최적의 상태란 현재 idx 이전의 전구는 모..