매석의 메모장

21553번: 암호 만들기 $B$가 $A$의 부분문자열이라는 것은 $A$의 왼쪽 끝과 오른쪽 끝에서 0개 이상의 문자를 제거해서 $B$를 만들 수 있음을 말합니다. 예를 들어 "123123"의 부분문자열로는 "123", "2312", "3", "123123" 등이 있 www.acmicpc.net 문제 당신은 폴리매스 왕국의 암호 개발자 친구로부터 개발을 요청받아 암호 제작을 돕기로 했습니다. 친구가 고안한 암호는 다음과 같이 작동합니다. 1에서 9까지의 숫자로 이루어진 문자열 A$A$와 B$B$가 있을 때, 이 둘이 공통으로 가지는 부분 문자열 중 길이가 K$K$인 것이 비밀번호가 됩니다. (부분문자열의 정의는 다음 페이지에 있습니다.) 예를 들어, A=1122$A=1122$, B=1223$B=1223$..

문제 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자. MenOfPassion 알고리즘은 다음과 같다. MenOfPassion(A[], n) { sum

문제 퐁당퐁당은 술게임 중 팀워크가 가장 중요한 MT 단골 게임이다. 매 차례마다 지정된 수의 팔을 동시에 들어야 하는데, 이를 실패하면 팔을 들어야했던 사람과 실수로 팔을 든 사람 모두 연좌제로 마셔야 하기 때문이다. 퐁당퐁당 게임의 규칙은 아래와 같다. 1번 사람부터 N번 사람까지 순서대로 총 N명의 사람들이 원 모양을 이루어 반시계방향으로 둘러앉는다. 이 때 모든 사람들은 원의 중앙을 바라보고 앉는다. 게임은 1번 사람의 왼팔부터 시작하여 원의 바깥에서 보았을 때 왼쪽에서 오른쪽으로 진행한다. 첫 번째 차례 이후 매 차례마다 가장 오른쪽 사람이 들었던 팔의 다음 팔부터 진행하고, 순서대로 지정된 수만큼의 팔을 들어올린다. 게임을 시작할 때 들어야 하는 팔의 갯수는 1개이다. 시작하여 차례가 지날 때..

25165번: 영리한 아리의 포탈 타기 아리가 보스 몬스터를 잡으러 가려면 광야에 위치한 포탈을 타야만 한다. 하지만 광야에는 아리가 포탈을 타러 가는 것을 방해하려는 보스 몬스터의 오른팔인 부하 몬스터 한 마리도 함께 위치 www.acmicpc.net 문제 아리가 보스 몬스터를 잡으러 가려면 광야에 위치한 포탈을 타야만 한다. 하지만 광야에는 아리가 포탈을 타러 가는 것을 방해하려는 보스 몬스터의 오른팔인 부하 몬스터 한 마리도 함께 위치해 있다. 광야는 세로의 길이가 N, 가로의 길이가 M 인 N x M 격자판으로 이루어져 있고 격자판의 왼쪽 윗 칸은 (1, 1)이며 오른쪽 아래 칸은 (N, M)이다. 아리가 처음 위치한 칸은 (1, Ac)이고, 부하 몬스터가 위치한 칸은 (Sr, Sc)이며, 포탈은..

문제 병역판정검사는 병역의무자들의 상태를 검사해 징병 여부와 징병 시 어느 방향으로 복무를 시키는 게 좋을지 판정하는 검사로, 남성들은 만 19세가 되는 해에 모두 병역판정검사를 받는다. 신체 등급이 1급부터 3급인 사람은 현역 입영 대상, 4급은 보충역, 5급은 전시근로역, 6급은 병역면제 처분을 받는다. 올해 20살이 된 준이와 친구들은 병역판정검사를 받아야 한다. 준이와 친구들은 매우 건강하기 때문에 다른 질병의 유무와 관계 없이 신장 및 체중으로만 신체 등급이 결정된다. 준이와 친구들의 신장과 체중이 주어지면 아래 표를 참고해 신체 등급을 알려주자. ↓신장(cm), 등급 → 1급 2급 3급 4급 5급 6급 140.1 미만 체중과 관계없이 6급 140.1 이상 146 미만 체중과 관계없이 5급 14..

문제 남서네 집 앞 편의점에는 각각 S, N, U의 이름이 붙은 총 3가지의 과자를 판다. 진열대에는 한 봉지당 가격과 무게가 안내되어 있다. 같은 종류의 과자끼리는 봉지의 무게가 똑같다. 남서는 오늘 과자를 10봉지 사려고 한다. 편의점의 단골인 남서는 할인 쿠폰 하나를 가지고 있는데, 총 구매 금액이 5,000원 이상일 때 500원을 깎아 주는 쿠폰이다. 구매 금액이 5,000원 미만인 경우에는 할인 쿠폰을 쓸 수 없다. 또한 할인을 여러 번 적용할 수는 없다. 남서는 과자를 고를 때 가성비를 중요하게 생각한다. 남서가 생각하는 가성비란, 총 무게를 총 금액으로 나눈 값이다. 남서는 빨리 과자가 먹고 싶기 때문에, 한 종류의 과자만을 10봉지 골라 사 가려고 한다. 또, 다른 물건은 구매하지 않을 생..

문제 에어팟에 여러 개의 핸드폰을 다음과 같은 방법으로 연결하고자 한다. 에어팟은 한 번에 하나의 핸드폰에만 연결이 가능하다. 에어팟을 새로운 핸드폰에 연결할 때마다, 기존 핸드폰과의 연결이 끊어지고, 에어팟 배터리 2퍼센트를 소모한다. 이미 연결되어 있는 핸드폰에 다시 연결을 시도할 때, 직전 배터리 소모량의 2배만큼 배터리를 소모하게 된다. 누적 배터리 소모량이 100퍼센트 이상이 될 경우, 에어팟을 충전시켜야 하기 때문에 현재 핸드폰과 에어팟의 연결을 해제한다. 이 경우 에어팟의 배터리 소모량은 0이 되고, 다음 핸드폰부터는 새로운 에어팟에 연결한다. 핸드폰의 종류는 1$1$부터 9$9$ 사이의 숫자로 나타내어지고, 에어팟에 연결한 순서대로 주어진다. 에어팟을 핸드폰에 연결한 횟수 N$N$과 각 차..

문제 2015, 2016년에 이어 2017년에도 연세대학교 교내 프로그래밍 경시대회가 열린다. 택희, 영훈이, 남규는 열심히 문제를 만들었고, 이에 대한 보상으로 과사로부터 사탕 N개를 받았다. N개의 사탕을 적절히 나눠 가지기 위해 토론한 결과, 아래와 같은 방식으로 사탕을 나누기로 결정하였다. 남는 사탕은 없어야 한다. 남규는 영훈이보다 2개 이상 많은 사탕을 가져야 한다. 셋 중 사탕을 0개 받는 사람은 없어야 한다. 택희가 받는 사탕의 수는 홀수개가 되어서는 안 된다. 이제 사탕을 적절히 나누어 집에 돌아가던 중, 택희는 위와 같은 규칙을 만족하도록 세 명에게 사탕을 나누어 주는 방법의 수가 궁금해졌다. 사탕의 개수 N이 주어지면, 사탕을 세 사람에게 분배하는 서로 다른 경우의 수를 세 보자. 문..

25175번: 두~~부 두부 두부 첫 번째 줄에 게임을 하는 사람의 수 $N$ ($1 \le N \le 100\,000$), 현재 차례인 사람의 번호 $M$ ($1 \le M \le N$), 부른 두부의 모 수를 나타내는 정수 $K$ ($-100\,000 \le K \le 100\,000$)가 주어진다. www.acmicpc.net 문제 시험이 끝난 준서는 친구들과 술을 마시고 있다. 두~~부 두부 두부 으쌰 으쌰 으쌰 두~~부 두부 두부 으쌰 으쌰 으쌰 어디선가 어깨를 주체할 수 없는 신명 나는 노랫소리가 들려오기 시작한다. 친구들은 홀린 듯 어깨춤을 추며 노래를 따라부르기 시작한다. 준서를 포함하여 N$N$명의 사람이 함께 노래를 부르며 게임을 진행하고 있다. 이름처럼 여러 글자를 말하기 힘들어진 사..

문제 어느 날 시계를 본 경근이는 시간이 8시 14분인 것을 보고 놀랐다. 왜냐하면 그의 생일은 8월 14일이기 때문이다. 그리고 이 경험을 바탕으로 다음과 같은 문제를 만들었다: 두 정수 x$x$, y$y$가 주어질 때, x$x$시 y$y$분으로 읽는 것이 가능한지의 여부를 판단하면서, x$x$월 y$y$일로 읽는 것이 가능한지의 여부를 판단하는 프로그램을 작성하라. 시는 0시에서 23시까지, 분은 0분에서 59분까지가 유효하며, 월은 1월에서 12월까지가 유효하다. 1월, 3월, 5월, 7월, 8월, 10월, 12월은 1일에서 31일까지가 유효하고, 4월, 6월, 9월, 11월은 1일에서 30일까지가 유효하며, 2월은 1일에서 29일까지가 유효하다. 문제풀이 import sys T = int(inpu..