시간 제한메모리 제한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)일 것 같다는 ..

이전 숫자에서 k개의 연속된 숫자를 외칠 수 있고 n을 외치면 승리하는 조건에서,n+1 길이의 dp를 생성하고, 필승패를 1로 표기, 나머지는 0으로 표기한다. [cpp]// 최선의 수를 둘 때 선공이 승리할 수 있으면 True#include using namespace std;bool NIM(int n, int k) { vector dp(n + 1, 0); for (int i = n; i > 0; i--) { for (int j = i + 1; j  [python]# 최선의 수를 둘 때 선공이 승리할 수 있으면 Truedef NIM(n, k): dp = [0] * (n + 1) for i in range(n, 0, -1): for j in range..

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

[정렬][탐색][기하]- 두 직사각형의 겹치는 영역 넓이 구하기 [동적계획법]- 님게임, 돌게임, 배스킨라빈스 31 게임 류

직사각형의 위치를 다음과 같이 두 점의 좌표로 표현하자.두 직사각형 (x1, y1), (x2, y2)와 (x3, y3), (x4, y4)가 있다.(x1 두 직사각형이 겹치는 영역은 다음과 같이 표현할 수 있다. [cpp]int area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0); [python]area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0)

ABC361의 모든 문제 중 가장 짧고 가장 이해하기 쉬운 문제였으나 간단한 설명과 달리 꽤나 치밀한 아이디어가 필요했고 그걸 떠올리는 과정이 재밌어서 정리를 남겨본다.시간 제한메모리 제한2초1024MB문제1이상 N이하의 정수 x에 대하여 어떤 정수 a와 2이상의 정수 b로 x = ab로 표현 가능한 것은 얼마나 있는가? 입력입력은 아래 형식의 표준입력으로 주어진다.N 조건입력은 전부 정수이다.1 ≤ N ≤1018출력답을 정수로 출력하시오. 입력예199 출력예112문제의 조건을 만족하는 정수는 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81으로 12개다. 입력예21000000000000000000 출력예21001003332 풀이조건에 맞는 정수인 a의 b거듭제곱 꼴로 나타내어..

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

1. 정점이 용량을 갖는 유량 그래프최대유량 문제에서는 간선으로 용량 정보가 주어진다. 근데 만약 정점에 용량이 있다면? 음의 유량 처리 과정에 문제가 생긴다. 포드 풀커슨의 방법에서 가장 핵심적인 아이디어는 음의 유량을 만들어 기존 유량을 우회시키는 테크닉이다.정점 중심으로 생각해보면 정점 3은 나가는 방향의 간선 용량의 총합인 3의 용량을 갖는다고 할 수 있다. 1→3의 유량 2를 우회시키면 s-2-3-5-t에 2의 유량을 흘려보낼 수 있다. 여기서 유량 우회가 가능한 이유는 유량을 간선 정보로 관리하고 있기 때문이다. u-v 간선 용량을 capa[u][v], u-v 간선의 현재 유량을 flow[u][v] 라고 표현하면 그래프 자체에서 u와 v의 순서로 간선의 방향 정보를 모두 관리하고 있는 셈이다...