넘치게 채우기

https://www.acmicpc.net/problem/17841BOJ - UNIST는 무엇의 약자일까?문제 유형: 다이나믹 프로그래밍문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제UNIST는 Ulsan National Institute of Science and Technology의 약자이다. 어느 날 원이는 약자가 UNIST가 되는 다른 단어가 있는지에 대해 궁금해졌다.단어 a의 길이를 len(a)로 표기하자. N개의 단어 W1, W2, ..., WN이 주어질 때, 단어 Wi (1 ≤ i ≤ N)로부터 앞에서 0글자 이상 len(Wi)글자 이하 택해서 만든 문자열을 Pi라 하자. 다시 말해, Pi는 Wi의 길이 len(Pi)인 접두사이다.Pi (1 ≤ i ≤ N)들을 적당..

https://www.acmicpc.net/problem/31005BOJ - 귤나무문제 유형: 애드 혹, 수학문제 난이도: Gold I시간 제한: 1초메모리 제한: 1024MB 문제서윤이네 뒷마당에는 M개의 귤이 열려 있는 커다란 귤나무가 있다.이웃집에 사는 N마리의 곰곰이들은 이 귤나무에 매일 귤을 따러 온다. 매일 1번 곰곰이부터 시작해서 N번 곰곰이까지 차례대로 귤을 따려고 시도하는데, i번 곰곰이는 A_i개의 귤을 따려고 시도하며 나무에 남은 귤이 A_i개 미만이라면 아무 행동도 하지 않는다. 10^{100} 일이 지났을 때, 귤나무에 남아있는 귤의 개수는 몇 개일지 구해보자. 입력첫째 줄에 곰곰이의 수와 귤의 개수 N, M이 공백으로 구분되어 주어진다. 1 1 둘째 줄에 각 곰곰이가 따갈 귤의..

https://www.acmicpc.net/problem/2698BOJ - 인접한 비트의 개수문제 유형: 다이나믹 프로그래밍문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128 MB 문제0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.예를..

https://www.acmicpc.net/problem/20553BOJ - 다오와 디지니의 데이트문제 유형: 그리디문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제크레이지 파크의 버블힐에도 새해가 찾아왔다. 다오와 디지니는 새해가 된 기념으로 데이트를 하며 버블힐의 곳곳을 둘러보려고 한다.버블힐은 직선 형태로 연결된 $N$개의 장소로 구성되어 있다. 버블힐에는 두 장소를 잇는 길이 $N-1$개 있는데, 1 이상 $N-1$ 이하의 각 정수 $i$에 대해 $i$번 장소와 $i+1$번 장소가 길로 연결되어 있다.다오와 디지니는 데이트 계획을 분 단위로 꼼꼼하게 세우려고 한다. 다오와 디지니는 매 분마다 다음의 세 가지 행동 중 하나를 선택하여 하려고 한다. 2 을 만족하는 i번 장소에..

https://www.acmicpc.net/problem/29333BOJ - One Walk문제 유형: 그래프, 애드 혹, 해 구성하기문제 난이도: Gold II시간 제한: 1초메모리 제한: 1024MB 문제무방향 단순 그래프 G가 주어진다. 이때, 어떤 정점 S로부터 다른 정점 E까지의 보행이 단 하나가 되도록 G의 모든 간선에 방향을 부여하여라. 그래프의 보행이란 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다. 입력첫째 줄에 정점과 간선의 개수 N, M, 시작점과 도착점의 번호 S, E가 공백으로 구분되어 주어진다. 둘째 줄부터 M개의 줄에 간선으로 연결된 두 정점의 번호 u, v가 공백으로 구분되어 주어진다. 출력모든 간선의 방향을 어떻게 정하여도 S에서 E까지의 보행이 단 하나가 되..

https://www.acmicpc.net/problem/15569BOJ - 블록 1문제 유형: 다이나믹 프로그래밍문제 난이도: Gold III시간 제한: 1초메모리 제한: 256MB 문제여러 가지 블록들을 이용하여 직사각형 모양을 만들려고 한다. 우리에게는 1 × N 블록, 2 × N 블록, ..., N × N 블록이 무한하게 있다. 이 블록들을 사용하여 N × M 모양을 만들고 싶다. 만들 수 있는 총 방법의 수를 1999로 나눈 나머지를 구하여라. 입력첫 번째 줄에 N과 M이 입력된다. (1 ≤ N ≤ 10^2, 1 ≤ M ≤ 10^4) 출력총 가능한 경우의 수를 1999로 나눈 나머지를 출력한다. 풀이dp[i][j] = i x j의 타일을 구성하는 경우의 수로 한다. 보통의 경우는 a x n짜리(..

https://www.acmicpc.net/problem/25306BOJ - 연속 XOR문제 유형: 수학, 비트마스킹문제 난이도: Gold IV시간 제한: 1초메모리 제한: 1024MB 문제준원이는 다음과 같이 A에서 B까지의 자연수들을 나열했다. A, A+1, A+2, \dots, B-2, B-1, B이 수들에 모두 비트 XOR을 취한 값을 구하라. 입력두 자연수 A, B가 공백을 사이에 두고 주어진다. 출력A 이상 B 이하인 모든 자연수들을 XOR한 값을 구하여라. 풀이물론 일일이 구하면 TLE에 걸린다.대신, f(x)를 1 ... x까지의 XOR sum이라고 해보자. 최종적으로 f(b) ^ f(a-1)을 구하면 되는 것이다. f(x), 즉 1 ... x의 XOR sum은 다음처럼 간단한 규칙을 가진..

https://www.acmicpc.net/problem/31791BOJ - 바이러스 공격문제 유형: 다익스트라, 그래프문제 난이도: Gold III시간 제한: 3초메모리 제한: 1024MB 문제무시무시한 테러 단체 '타도 유해조류 산지니'가 부산대학교에 바이러스를 살포하겠다고 예고했다. $N$행 $M$열의 격자로 이루어진 부산대학교 위에는 B개의 건물이 구역 안에 겹치지 않고 있으며, 부산대학교의 철통같은 보안 덕에 테러 단체가 건물에는 바이러스를 살포하지 못한다.테러에 사용될 바이러스는 아래의 세 가지 특징이 있다.건물의 내부와 외부에 존재하는 모든 바이러스는 살포 시점으로부터 T_{G}시간 뒤 전파를 멈춰 바이러스가 더 이상 주변으로 퍼지지 않는다.바이러스로부터 안전하지 않은 구역과 상하좌우로 인접..

https://www.acmicpc.net/problem/27896BOJ - 특별한 서빙문제 유형: 우선순위 큐, 그리디문제 난이도: Gold V시간 제한: 1초메모리 제한: 512MB 문제???: 가지라니, 비슷하지도 않잖아요...NLCS Jeju에서는 파묻튀(파마산을 묻혀 튀긴 소고기)를 서빙하는 것을 좋아한다.그러나, 학생들은 파묻튀보다는 신선한 가지를 먹고 싶어한다!급식실에 N명의 학생들이 차례로 서 있다. 줄의 앞에서부터 i번째 학생이 가지 대신 파묻튀를 받았을 경우 x_i만큼 불만도가 늘어나고, 가지를 받았을 경우에는 x_i만큼 불만도가 내려간다. 단, 불만도의 초깃값은 0이다.음식을 앞에 서있는 학생부터 순서대로 서빙할 때, 어떤 한 순간이라도 불만도가 M 이상이 되면 학생들은 ‘가지 운동’..

https://www.acmicpc.net/problem/24419BOJ - 알고리즘 수업 - 행렬 경로 문제 2문제 유형: 조합론, 수학문제 난이도: Silver II시간 제한: 1초메모리 제한: 512MB 문제오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.양의 정수로 이루어진 n × n 행렬 m이 주어진다. 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동 규칙은 다음과 같다.오른쪽이나 아래쪽으로만 이동할 수 있다.왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.행렬의 원소 (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 ..