시간 제한메모리 제한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번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다. 백준이가 책을 줄 수 있는 최대 학생 수를 구하시오. 입력첫째 줄에 테스트 케이스..

시간 제한메모리 제한1초512MB문제https://www.acmicpc.net/problem/14750풀이다양한 알고리즘이 혼합된 문제다. 하지만 기본 개념 적용만 잘하면 까다로운 부분은 없어서 어렵지 않게 해결 할 수 있는 문제!..(맞나?) 문제에서 요구하는 것은 쥐구멍에 들어갈 수 있는 최대 쥐의 마릿 수다. 쥐는 쥐구멍까지 이어지는 일직선 상에 다른 벽과의 어떤 접점도 없어야만 해당 쥐구멍에 들어갈 수 있고, 각 쥐구멍에는 도망갈 수 있는 쥐의 수 제한이 있다. 우선은 쥐가 어떤 쥐구멍으로 도망갈 수 있는지 확인해야 한다.  1. 선분 교차 판정으로 쥐와 쥐구멍의 연결 여부 확인쥐의 위치를 m, 쥐구멍의 위치를 h, 벽의 양 끝 점을 a, b라고 하면 아래 그림과 같은 상황에서 ccw 값을 얻을 ..

시간 제한메모리 제한1초512MB문제UCPC에는 N명의 사람이 있다. 먼 옛날 쇼킹핫치킨에 대한 논쟁에서 시작된 이념의 대립으로 UCPC에는 kriii를 따르는 쇼킹핫진보 진영 A와, august14를 따르는 쇼킹핫보수 진영 B의 두 진영이 존재한다. 모든 사람은 둘 중 한 진영에 소속되어 있으며, 두 진영에 동시에 들어가는 것은 불가능하다. i번 사람과 j번 사람에 대해 서로 다른 진영에 들어가게 될 경우 슬픈 정도 w[i, j]가 주어진다. 일부 사람들은 쇼킹핫에 관한 자신의 철학이 강해 무조건 A진영에 들어가는 사람도 있고, 무조건 B진영에 들어가는 사람도 있다. 물론 치킨은 무엇이든 옳으므로 두 진영 어디에 가든 상관없는 사람도 있다. N명의 사람들이 적절히 두 진영에 나누어 들어갈 때, 슬픔 정..

시간 제한메모리 제한2초1024MB문제사람들이 N행 M열의 직사각형 모양으로 모여 있다. 초기에 각각의 사람의 상태는 정상 체온이거나 저체온증이고, 낮과 밤을 지나면서 사람들의 상태가 변화한다.낮은 따뜻하기 때문에 저체온증인 사람이 정상 체온으로 회복할 수 있는 기회이다. 어떤 사람과 사방으로 인접한 두 명 이상의 사람이 정상 체온이라면 따뜻한 체온을 나눠 받아 저체온증에서 정상 체온으로 회복된다. 어떤 사람이 정상 체온으로 회복된 후에는 같은 방법으로 인접한 다른 사람들이 정상 체온으로 회복할 수 있으며, 이러한 체온 회복 과정은 낮 사이에 충분히 많이 반복될 수 있다.밤은 춥기 때문에 정상 체온인 사람들이 저체온증에 걸릴 수 있다. 단, 밤 사이에 새롭게 저체온증에 걸리는 사람은 K명 이하이다.낮과 ..

23829번: 인문예술탐사주간 태영이는 SASA의 축제라고 불리는 "인문예술탐사주간"을 보내게 되었다. "인문예술탐사주간"을 맞이하여 세종호수공원에 가게 된 태영이는 아름다운 경치에 놀라움을 금치 못했다. 세종호수공원 www.acmicpc.net 만약 태영이의 위치가 0이라면 사진의 점수는 모든 나무의 위치 총합이 된다. 태영이의 위치가 X일 때, X 오른쪽 나무들로 얻는 점수는 각 나무의 위치에서 X를 뺀 값의 총 합이 된다. X 왼쪽 나무들의 점수는 X에서 나무의 위치를 뺀 값의 총합이 된다. 결국 점수는 특정 위치로부터의 누적합이 되는 셈이다. i번째 나무까지의 누적합을 prepix[i]에 저장한다. 그림으로 보면 아래와 같다. 태영이가 13에 있다면 a와 b는 이렇게 그려볼 수 있다. 파란색이 빼..