넘치게 채우기

https://www.acmicpc.net/problem/6506BOJ - 엘 도라도문제 유형: 다이나믹 프로그래밍문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제상근이는 라스베가스의 엘 도라도 카지노에 도착했다. 태어나서 카지노에 처음 가본 상근이는 휘황찬란한 카지노의 내부에 입을 다물 수 없었다. 그런 그의 눈길을 사로 잡는 게임이 하나있었다. 그 게임은 화면에 n개의 숫자가 화면에 뜨는 아주 단순해 보이는 게임이었다. 이 게임의 참가자는 컴퓨터가 만드는 수열에서 길이가 k인 증가하는 부분 수열의 개수를 예상해야 한다.수열 a1, ..., an의 부분 수열은 1 ≤ i1 ≤ n를 만족하는 ai1, ..., ail로 정의 한다. 부분 수열이 증가하려면 모든 1 상근이는 다른 ..

https://www.acmicpc.net/problem/13713BOJ - 문자열과 쿼리문제 유형: 문자열, Z 알고리즘문제 난이도: Platinum V시간 제한: 2초메모리 제한: 128MB 문제문자열 S = S_1S_2...S_N이 주어진다. 함수 F(i)는 S와 S_1S_2...S_i의 가장 긴 공통 접미사의 길이로 정의된다.예를 들어, S = "zaaxbaacbaa"인 경우에, F(1) = 0, F(2) = 1, F(3) = 2이다.문자열 S와 쿼리 M개가 주어졌을 때, 각각의 쿼리에 대해서, F(i)를 구하는 프로그램을 작성하시오. 입력첫째 줄에 문자열 S가 주어진다. (1 ≤ N ≤ 1,000,000)둘째 줄에 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)셋째 줄부터 M개의 줄..

https://www.acmicpc.net/problem/27232BOJ - 청소문제 유형: 집합, 슬라이딩 윈도우문제 난이도: Gold I시간 제한: 2초메모리 제한: 1024MB 문제준석이는 청소 업체에 다니고 있다. 준석이가 청소할 장소는 1번부터 N번까지 차례로 번호가 붙은 일렬의 1N개의 구역으로 나누어져 있다. i번 구역은 i-1번과 i+1번 구역과 인접해 있어, 두 인접한 구역 사이를 이동하려면 1만큼 걸어야 한다.각 구역에는 우선순위가 있다. i번 구역의 우선순위 A_i는 1이상 N이하의 정수로 이 값이 클수록 우선순위가 높다. 임의의 두 구역의 우선순위는 항상 다르다.준석이는 오늘 이 구역 중 K개의 구역을 먼저 청소하려고 한다. 단, 준석이가 청소하는 K개의 구역은 반드시 연속해야 한다..

https://www.acmicpc.net/problem/3217BOJ - malloc문제 유형: 구현, 집합과 맵(set, map), 문자열 처리문제 난이도: Gold I시간 제한: 1초메모리 제한: 128MB 문제메모리 할당 명령을 시뮬레이팅하는 프로그램을 작성하시오.메모리는 100,000개의 연속된 공간이고, 1번부터 100,000번까지 번호가 매겨져 있다. 초기에 모든 공간은 할당되지 않은 상태이다.명령어의 종류는 다음 중 하나이다.var=malloc(size);이 함수은 처음 등장하는 size개의 연속된 공간을 찾아, 할당해주는 함수이다. 이 함수의 리턴값은 할당된 공간의 제일 처음 주소이다. 만약, 할당해줄 수 있는 공간이 없다면 0을 리턴한다. (100 ≤ size ≤ 100,000)free..

https://www.acmicpc.net/problem/12004BOJ - Closing the Farm문제 유형: bfs/dfs, 그래프문제 난이도: Gold IV시간 제한: 2초메모리 제한: 512MB 문제Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporarily close down his farm to save money in the meantime.The farm consists of N barns connected with M bidirectional paths between some pairs of barns (1 ). To shut the farm down, FJ ..

https://www.acmicpc.net/problem/1263BOJ - 시간 관리문제 유형: 정렬, 그리디문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.진영이가 바라..

https://www.acmicpc.net/problem/30190BOJ - 여우의 꿈문제 유형: 수학, 그리디, 재귀문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제여우 마을에는 3개의 기둥과 N개의 원판을 가진 하노이 탑의 원판들을 한 곳에 모으면 소원이 이루어진다는 전설이 있다.하노이 탑의 원판들을 이동시키는 규칙은 다음과 같다.i번째 원판의 반지름은 i이다. (1 )어떤 시점에라도 한 기둥 안의 원판은 반지름이 작을수록 위로 오도록 정렬되어 있어야 한다.각 기둥의 제일 위에 있는 원판만 이동할 수 있다.원판은 기둥의 맨 위로만 이동할 수 있다.원판은 한 번에 한 개만 이동할 수 있다.여우 마을에 사는 아기 여우는 어느 날 이 소문을 듣고 하노이 탑에 도전하기로 했다. 아기 ..

https://www.acmicpc.net/problem/2938BOJ - 3으로 나누어 떨어지지 않는 배열문제 유형: 애드 혹, 해 구성하기, 많은 조건 분기문제 난이도: Gold V시간 제한: 1초메모리 제한: 256MB 문제자연수로 이루어진 배열이 주어졌을 때, 수의 순서를 적절히 바꿔서 인접한 두 수의 합이 3으로 나누어 떨어지지 않는 배열을 만드는 프로그램을 작성하시오. 입력첫째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 10000)둘째 줄에는 배열에 들어있는 수가 공백으로 구분되어 주어진다. 수는 1,000,000보다 작거나 같은 자연수이다. 출력만약, 3으로 나누어 떨어지지 않게 배열을 만들 수 있다면 첫째 줄에 출력한다. 불가능하다면 -1을 출력한다. 풀이0을 나머지가 0인 수들, ..

https://www.acmicpc.net/problem/17255BOJ - N으로 만들기문제 유형: 브루트 포스, 백트래킹문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다.처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다.다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다.수의 왼쪽에 숫자를 하나 적는다.수의 오른쪽에 숫자를 하나 적는다.준하는 어떤 수 N을 만드는 방법의 수가 몇 가지인지 궁금해졌다. 이를 알아내는 프로그램을 작성해주자. 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방..

https://www.acmicpc.net/problem/19646BOJ - Random Generator문제 유형: 세그먼트 트리, 이분 탐색문제 난이도: Platinum V시간 제한: 1초메모리 제한: 1024MB 문제국렬이는 1부터 N까지의 양의 정수로 이루어진 순열을 주어진 양의 정수 w1 ... , wN를 이용해서 무작위로 만들 것이다. 다음은 무작위로 순열을 만드는 방법이다.1부터 N까지의 양의 정수 i (1 ≤ i ≤ N)를 연속적으로 wi개씩 배치한다.현재 배치된 양의 정수의 총 개수를 W라고 하자. 1부터 W까지의 양의 정수들 중에서 균등하게 숫자 하나 pi를 선택한다.pi번째 수를 순열에 추가한다.순열에 추가한 수들을 전부 지우고, 남은 수가 없을 때까지 2부터 4의 과정을 거친다.w1..