[programmers/kakao] 징검다리 건너기
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/64062?language=java 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 징검다리에 돌이있다. 이 돌에는 밟을수있는 횟수가 정해져있으며, 한번 밟을때마다 횟수가 줄어든다. 또한, 징검다리를 건너뛸수있는 최대 길이 k 가 주어진다. 한 사람이 징검다리를 한번 건널때 밟을 수 있는 모든 돌을 밟는다 했을때, 최대 몇명의 사람이 징검다리를 건널 수 있는지 구하는 문제다. 문제를 읽어보면, "밟을 수 없는돌의 연속길이가 k가 되는지점"을 구하는 문제임을 알수있다. 징검다리의 길이가 200,000 이기때문에, 완전탐색..
[백준 / 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..