량베개

프로그래머스 쿠키 구입 LV4   문제 설명과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다. 철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 . 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다. 각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solut..

프로그래머스 도둑질 LV4 문제도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.제한 사항이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.moneyreturn[1,2,3,1]4   문제에서 조심해야 하는 경우는 2가지이다.1. 이전 집을 도둑질 하고 다음 집도 도둑질을 하는 경우2. 처음 집을 도둑질을 하고 마지막 집도..

1948번 임계경로 P5 문제월드 나라는 모든 도로가 일방통행인 도로이고, 사이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트하여라. 출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로..

프로그래머스 호텔 방 배정 LV4 "스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.한 번에 한 명씩 신청한 순서대로 방을 배정합니다. 고객은 투숙하기 원하는 방 번호를 제출합니다. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음..

1939번 중량제한 G3 문제N(2 ≤ N ≤ 10,000) 개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다. 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 ..

2152번 여행 계획 세우기 P2  문제평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1 ≤ N ≤ 10,000) 개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을 거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다. 태희는 다시 비행로에 대해 조사를 하였고, 총 M(1 ≤ M ≤ 100,000) 개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1 ≤ S ≤ N) 번 도시에서 시작해서 T(1 ≤ T ≤ N) 번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다.도..

프로그래머스 야근 지수 LV3 문제 설명회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.제한 사항works는 길이 1 이상, 20,000 이하인 배열입니다.works의 원소는 50000 이하인 자연수입니다.n은 1,000,000 이하인 자연수입니다.입출력 예worksnresult4[4, 3, 3]121[2, 1, 2]63[1, 1..

17297번 Messi Gimossi G4 문제메시는 축구 선수이다. 메시는 기분이 좋다.messi(1): Messimessi(2)​​: Messi Gimossimessi(3)​​​​​​: Messi Gimossi Messimessi(4): Messi Gimossi Messi Messi Gimossimessi(5): Messi Gimossi Messi Messi Gimossi Messi Gimossi Messi메시의 외침은 피보나치수열과 유사하게 정의된다.messi(N)은 messi(N-1), 공백, messi(N-2)을 차례로 이어붙여서 만든 문자열이다. 욱제는 N이 충분히 클 때, messi(N)의 M번째 글자가 뭔지 궁금해졌다.입력정수 M이 주어진다. (1 ≤ M ≤ 2^30-1)출력N이 충분히 클..

1516번 게임 개발 G3  문제숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다. 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 ..

최장 증가 부분 수열(LIS)에 해당하는 문제 시리즈이다.입력과 출력, 시간 복잡도와 수의 범위에 따라 S2에서 P5까지 난이도가 준비되어 있다. 문제를 풀 당시에는 1 -> 4 -> 2 -> 3 -> 5 순으로 풀이했다.LIS를 처음 접한다면 위 순서대로 푸는 것이 좋을 것이라 생각한다. 11053번 가장 긴 증가하는 부분 수열 / S2수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다. 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있..