분류 전체보기

문제여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.빈 문자열은 안정적이다.S가 안정적이라면, {S}도 안정적인 문자열이다.S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.입력입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘..

문제상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로..

문제은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,SN번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a개, 뒤에서 b개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b번 과일, 총 N−(a+b)개가 꽂혀있는 탕후루가 됩니다. (0≤a,b; a+b이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.입력..

문제산들이는 포도주(와인)를 좋아한다. 그는 마트에서 팔고 있는 N$N$종류의 포도주를 사서 음미하려고 한다. 포도주를 한 병 단위로 사기엔 산들이가 금전적으로 부담이 있기 때문에 그는 작은 용기에 담긴 포도주를 살 것이다. 마트에서 팔고 있는 N$N$종류의 포도주들은 각각 T1$T_1$, T2$T_2$, …, TN$T_N$의 맛을 갖고 있다. 맛의 값이 높은 포도주가 더 맛있는 포도주이다.산들이가 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 그 맛이 감기약 맛을 방불케 하기 때문에 사실상 0의 맛을 느낀다. 하지만 맛없는 포도주를 마시다가 맛있는 포도주를 마시면 그 두 포도주의 맛 차이만큼 맛을 느낀다. 예외적으로 가장 먼저 마시는 포도주의 맛은 그 포도주 본연의 맛 그대로이다.산들이는 주량이 매우..

문제더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.우리 안은 1차원 배열로 생각하며, 총 N(1 ≤ N ≤ 100000)개의 얼음 양동이들이 xi(0 ≤ xi ≤ 1,000,000)좌표마다 놓여 있고 각 양동이 안에는 gi(1 ≤ gi ≤ 10,000)씩의 얼음이 들어 있다. 일단 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤ 2,000,000) 만큼 떨어진 양동이까지 닿을 수 있다. 앨버트는 양동이가 놓여 있는 자리에도 자리잡을 수 있다. 모든 얼음 양동이의 위치는 다르다.앨버트가 최적의 자리를..

문제드높은 남산 위에 우뚝 선(중략)세워라 반석 위에선린의 터를반석: 넓고 펀펀한 큰 돌, 너럭바위어떤 수열이 반석이라는 것은, 수열의 최댓값과 최솟값의 차이가 2 이하임을 의미한다.예를 들어 1 2 3 3 1 2는 최댓값(3)과 최솟값(1)의 차이가 2이므로 반석이고, 2 6 5 4는 최댓값(6)과 최솟값(2)의 차이가 4이므로 반석이 아니다.수열이 주어지면 수열의 연속한 부분 수열(부분 문자열, substring) 중, 가장 긴 반석의 길이를 구하는 프로그램을 작성하자.입력첫 번째 줄에 수열의 길이 N$N$이 주어진다.두 번째 줄에는 수열 A의 원소 A1,A2,⋯,AN이 공백으로 구분되어 주어진다.출력수열 A의 연속한 부분 수열 중 가장 긴 반석의 길이를 출력한다. 접근 방식 투 포인터를 사용하면 될..

문제올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다. (연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오.입력첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 배열에 중복되는 수는 없다.출력 첫째 줄에 입력으로 주어진..

문제There are n houses along the road where Anya lives, each one is painted in one of k possible colors.Anya likes walking along this road, but she doesn't like when two adjacent houses at the road have the same color. She wants to select a long segment of the road such that no two adjacent houses have the same color.Help Anya find the longest segment with this property.입력The first line contains t..