[백준 / BOJ] 17383 옥토끼는 통신교육을 풀어라!!
문제 출처 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 옥토끼는 두개의 문제를 한번에 풀수있다. N개의 문제가 주어질때, 문제를 푸는 시간사이의 공백을 최소화하는 시간을 구하는 문제다. 풀이 결정문제로 풀은 문제였다. Ni가 최대 10억이고, 완전탐색으로 풀경우, 최소 max(Ni)*(a), (a>N)시간복잡도가 나와서, 항상 시간초과가 나온다. 위의 식 N*(a)의 시간을 줄이는 방법은 다음과 같다. 1. N N이 의미하는것은, 모든..
[백준 / BOJ] 21319 챔피언(Easy)
문제 출처 : https://www.acmicpc.net/problem/21319 21319번: 챔피언 (Easy) 1번 선수는 어떻게 해도 챔피언이 될 수 없다. 2번 선수는 어떻게 해도 챔피언이 될 수 없다. 3번 선수는 (2, 3), (1, 3), (3, 4) 순서대로 격투가 일어나면 챔피언이 될 수 있다. 4번 선수는 (3, 4), (2, 4), www.acmicpc.net N명의 선수가 비 내림차순으로 주어진다. 각 선수는 자신의 양쪽선수와 경기를 하며 파워가 더 쌘 선수가 승리한다. 승리시 자신의 파워가 +1 증가하며, 패배한 선수의 양쪽 선수와 연결된다. 위 과정을 반복후, 경기장에 혼자 남아있을때, 그 선수를 챔피언 이라고 한다. 이때, 챔피언이 될 가능성이 있는 선수를 모두 구하는 문제다..
[백준 / BOJ] 1561 놀이 공원
문제 출처 : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 놀이공원에 N명의 사람과, M개의 놀이기구가 있다. M개의 놀이기구는 각각 운행시간이 있으며, N명의 사람은 놀이기구를 "현재 탑승가능한 놀이기구중 빠른번호 순서"로 탑승하려고한다. 이때, 마지막사람이 탑승할 놀이기구의 번호를 출력하는 문제다. 풀이 처음 문제를 봤을때는, 스킵하는 방식의 dp를 이용한 문제일거라고 생각했는데, N이 최대 2,00..
[백준 / BOJ] 15732 도토리 숨기기
문제 출처 : https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 수형이는 N개의 상자에 도토리를 숨기려한다. 이때, 도토리를 숨긴위치를 기억하기 쉽게하기위해 규칙있게 숨긴다. 예를들어, A상자부터 B상자까지 C간격으로 도토리를 숨긴다면, A 상자에 하나를 숨기고, A+C상자에 하나를 숨기고, A+2C상자에 하나를 숨기고..B상자에 마지막하나를 숨긴다. 상자의 수..