dev_lee

문제https://www.acmicpc.net/problem/1593마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알..

문제https://www.acmicpc.net/problem/12891평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의..

문제https://www.acmicpc.net/problem/29718오늘은 많은 학생이 기다리던 브실브실 학교의 축제 행사 날이다.브실이는 학교 축제 담당자로서 축제의 분위기가 잘 살아날 수 있도록 무대 앞에 N행 M열로 의자를 하나씩 배치해 두고 각 의자에 응원단 사람을 1명씩 뒀다.브실이는 응원단의 사기를 확인하기 위해 연속된 A개 열 중 가장 박수 횟수가 많은 곳을 찾고자 한다. 즉, 1열부터 A열, 2열부터 A+1열, 3열부터 A+2열, ⋯, M−A+1열부터 M열에 대해 각 구간에 속하는 응원단 사람들에게 박수를 치게 해서 그중 가장 많이 박수를 친 구간의 박수 횟수를 찾고자 한다.하지만 브실이는 지금 학교 축제 담당자로서 할 일이 많아 이 일은 우리에게 맡기고 다른 일을 하러 갔다.각 응원단 ..

문제https://www.acmicpc.net/problem/1522a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.예를 들어, aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.입력첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.출력첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.풀이1. 먼저, 문자열 내에 있는 'a'의 개수를 센다. 이는 연속으로 만들고자 하는 'a'의 총 개수이다.2. 문자열이 원형이므로, 처음과 끝이 이어질 수 있도록 문자열을 뒤에 이어 붙인다.3. 이어 붙인 문자열에..

문제https://www.acmicpc.net/problem/29700도은이는 동아리 문화의 날을 맞이하여 동아리원들과 함께 좌석이 M행 N열의 직사각형 모양으로 배치되어 있는 영화관에서 영화를 보기로 했다. 도은이는 동아리원의 유대감을 중요하게 생각하기 때문에 이미 예매가 완료된 좌석을 피해 동아리원들이 모두 가로로 이어서 앉을 수 있도록 자리를 예매하고 싶어 한다. 도은이를 도와 모든 동아리원들이 가로로 이어서 앉을 수 있도록 예매하는 경우의 수는 총 몇 가지가 있을지 구해보자. 단, 예매한 좌석은 동일하지만, 각 사람이 앉는 위치만 바뀌는 경우는 한 가지로 본다.입력첫째 줄에 영화관 세로줄의 개수 N(1≤N≤1000)과 가로줄의 개수 M(1≤M≤5000), 영화를 관람할 동아리원의 수 K(1≤K≤1..

문제https://www.acmicpc.net/problem/2559매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합이 가장 큰 값은 21이다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.입력첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구..

문제https://www.acmicpc.net/problem/15565꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라.입력첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106)둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2)출력K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다.풀이1. 라이언 인형의 인덱스만 따로 저장한다.2. 라이언 인형이 K개 미만일 경우, -1을 출력한다.3. 저장된 인덱스를 기반으로, K개씩 슬라이딩 윈도우를 이동시키며 각 구간의 길이..

문제https://www.acmicpc.net/problem/14465농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.입력첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.출력정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력..

문제https://www.acmicpc.net/problem/24499오늘도 블롭은 배고프다. 그래서 블롭은 요리사 연우를 찾아가 맛있는 것을 달라고 부탁했다.연우는 귀여운 블롭에게 이왕이면 맛있는 음식을 해 주고 싶었기에, 자신이 만드는 데에 가장 뛰어난 애플파이를 만들기로 하였다. 연우는 N개의 애플파이를 만들었으며, 이를 원 모양으로 책상에 배치해 놓았다.각 애플파이는 하나의 양의 정수로 표현되며, 이는 맛있는 정도를 의미한다. (수가 클수록 더 맛있는 애플파이이다.)블롭은 N개의 애플파이 중 K개를 먹으려고 한다. 물론 블롭은 힘을 들이지 않고 먹고 싶기 때문에, 연속으로 배치되어 있는 K개의 애플파이를 먹으려 한다.블롭을 도와서 블롭이 먹을 애플파이의 맛의 합의 최댓값을 구해 주자!입력첫째 줄에..