시간 제한메모리 제한1초128MB문제상근이는 서강 프로그래밍 대회의 문제를 준비해야 한다. 모든 문제의 난이도는 1과 N사이의 자연수로 표현할 수 있다. 하지만, 어떤 문제는 난이도를 정확하게 결정할 수 없는 경우도 있다. 따라서, 상근이는 문제의 난이도를 숫자 하나 또는 연속한 두 수로 표현하기로 했다. 예를 들어, 어떤 문제의 난이도는 3 또는 4가 될 수 있다. 올해 대회는 총 N문제가 필요하다. 상근이는 각 난이도에 해당하는 문제를 한 문제씩 내기로 했다. 당연하겠지만 같은 문제를 두 번 낼 수는 없다. 이때, 문제를 고르는 경우의 수를 구하는 프로그램을 작성하시오. 어떤 난이도에 해당하는 문제가 다른 경우에 두 방법이 서로 다른 경우이다. 정답이 매우 커질 수 있으므로 경우의 수를 1,000,0..

시간 제한메모리 제한1초512MB문제SASA의 자습 시간에는 매일마다 정독실, 소학습실, 휴게실, 그리고 방에서 휴식을 취할 수 있는 요양 4가지 중 하나를 선택할 수 있다. 우석이는 자습 장소에 따라 얻을 수 있는 만족도가 있으며, 그 4가지 값은 매일 우석이의 기분에 따라 결정된다. 우석이는 자습을 총 N일 동안 해야 하며, 기숙사에는 다음과 같은 규칙이 있다.요양 신청은 최대 A회 가능하다.휴게실에서 이틀 연속으로 자습을 할 경우, 게임을 하는 것으로 판단되어 퇴사 처리된다.정독실이나 소학습실에서 자습을 총 B회 미만으로 할 경우, 학습 의지 상실로 판단되어 퇴사 처리된다.공부하기 싫은 우석이가 퇴사를 당하지 않고 기숙사의 규칙을 지키면서 N일 동안 얻을 수 있는 만족도의 합의 최댓값을 구해보자.입..

시간 제한메모리 제한2초128MB문제N(1≤N≤200)개의 도시로 이루어진 나라가 있다. 이 도시들 사이를 다니는 고속철도망을 만들어 도시 간의 이동을 편하게 하려고 한다. 단, 고속철도망을 만든 후에 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있게 하려고 한다. 시범 사업으로 몇 개의 도시 사이에 고속철도가 설치되었는데 그 결과가 매우 좋아 국가에서는 이 사업을 완성하기로 하였다. 이제 당신은 몇 개의 도시 사이에 고속철도를 추가로 설치하여, 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있게 하려고 한다. 그러나 이 사업은 워낙 돈이 많이 드는 사업이기 때문에, 이 사업에 드는 총 비용을 최소화 하려고 한다. 두 도시 사이에 고속철도를 설치할 때 드는 비용이..

시간 제한메모리 제한1초512MB문제방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다. 백남이는 여행에 필요하다고 생각하는 필수품 N개를 가지고 있다. 각 물건은 무게 W와 가치 V를 가진다. 그리고 백남이는 물건을 담을 가방 M개를 가지고 있는데, 각각의 가방은 최대 Ki만큼의 무게를 견딜 수 있다.MBTI가 J(판단형)인 백남이는 효율성을 중요하게 여기기 때문에, 가장 효율적으로 짐을 싸지 않으면 여행을 출발할 수 없다. 백남이가 정의한 효율성은 (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다.가방과 물건의 정보가 주어졌을 때, 가장 효율적으로 짐을 싸기 위해 필요한 가방이 무엇인지 알아내자. 가방은 한 개만 선택할 수 있으며, 최적의 가방이 여러 가지라면 그중 ..

시간 제한메모리 제한1초1024MB문제 길이가 4 이상인 영어 대문자로만 이루어질 수 있는 서로 다른 모든 문자열에 대해, 0개 이상의 문자를 제거하였을 때 문자열 MRDR이 되는 문자열을 MR.DR 문자열이라고 한다. 정수 N이 주어질 때, 길이가 N인 MR.DR 문자열의 개수를 구하는 프로그램을 작성하라. 입력첫 번째 줄에 정수 N이 주어진다. ( 4 ≤ N ≤ 100,000) 출력길이가 N인 MR.DR 문자열의 개수를 출력하라. 이때 정답이 매우 커질 수 있으므로 정답을 1,000,000,007 (=109 + 7)로 나눈 나머지를 출력하라.풀이 시간 제한이 1초, N의 범위가 100,000까지인 것으로 보아 최소한 O(NlogN)으로 끝내야 한다. 근데 이분탐색 요소는 없으니 O(N)일 것 같다는 ..

시간 제한메모리 제한1초512MB문제두 명의 학생이 1이상 n이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 후 두 명의 학생이 교대로 정수를 외친다. 이전 학생이 외친 정수가 a이면 현재 학생은 (a + 1)이상 (a + k)이하의 정수를 외쳐야 한다. 맨 처음 첫 번째 학생은 1이상 k이하의 정수를 외쳐야 한다. 추가로, 두 명의 학생이 외칠 수 없는 정수 목록이 주어지고, 두 명의 학생은 목록에 있는 정수를 외칠 수 없다. 마지막에 정수를 못 외치는 학생이 게임을 진다. 현재 학생이 외칠 수 있는 정수가 여러 개이면, 외칠 수 있는 정수 중 하나를 외친다. 두 명의 학생이 규칙에 맞게 플레이했을 때, 첫 번째 학생이 이기면 1을 출력하고 두 번째 학생이 이기면 0을 출력한..

시간 제한메모리 제한1초128MB문제아래에 주어진 전개도의 점선 부분을 접어서 주사위 모양의 정육면체를 만들 수 있는지를 생각해 보자. 전개도의 각 면은 1에서 6까지 서로 다른 정수로 표시되어 있다.전개도 (1)은 정육면체로 접을 수 있지만, 전개도 (2)는 정육면체로 접을 수 없다. 입력으로 주어진 전개도를 정육면체로 접을 수 있는지를 알아보는 프로그램을 작성하시오. 입력입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나타낸다. 출력입력된 전개도를 정육면체로 접을 수 있으면, 정육면체에서 1번으로 표시된 면의 맞은 편 면의 번호를 출력하고, 정육면체로 접을 ..

시간 제한메모리 제한2초256MB문제백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다. 조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다. 백준이가 책을 줄 수 있는 최대 학생 수를 구하시오. 입력첫째 줄에 테스트 케이스..