본문 바로가기

알고리즘/코드포스-퍼플까지 도전기

 (3)
[codeforce]#526 (Div. 2) C. The Fair Nut and String 문제 출처 : http://codeforces.com/contest/1084/problem/C 문제 요약 연속된 'a' 의 부분집합의 갯수 구하기단, 연속된 조건은 가운데 'b'가 있어야 연속예를 들어, 'aba' 는 {1}, {3}, {1, 3} 이런 식으로 부분집합을 구할 수 있으면, 여기서 1, 3 은 연속된 집합이라고 할 수 있음. 문제 풀이 'abbaa' 인 경우, {1}, {4}, {5}, {1, 4}, {1, 5} 와 같이 부분집합의 갯수를 셀 수 있다. 즉, 연속하기 위해선 2개의 'a' 원소 사이에 연속된 1개 이상의 'b' 원소가 포함되어야한다.--> 연속된 b원소를 기준으로 나눠보자 a /(bb)/ aa -> (1)개 / (2)개 이와 같이 표현할 수 있다. 따라서, (첫번째 구간에서..
[codeforce] #526(Div. 2) B. Kvass and the Fair Nut 문제 링크 : http://codeforces.com/contest/1084/problem/B 문제 정리 n 개의 서로 다른 양의 물(vL)을 가지고 있는 물통이 있다철수는 sL를 담을 수 있는 물컵이 있다여기서 서로 다른 양의 물통 중, 가장 적은 물통의 양을 최대로 하는 방법을 구하라. 문제 풀이 3개의 물에 5 / 3 / 4 리터가 있다고 가정하자. 여기서 가장 적은 물의 양은 3 리터이다. 가장 적은 물의 양을 제외하고 나머지 물의 양을 받으면 받은 물의 양 = (5 - 3) + (5 - 4) = 3 리터이다. if ( 받은 물의 양 >= 물컵의 양 ) 이면, 정답은 3리터이지만, 아닌 경우, 현재 물통의 상황은 3 / 3 / 3 이럴 것이다. 여기서 한개의 물통에서 1리터만 빼어도 가장 적은 물..
[codeforce] #526 (Div. 2) A. The Fair Nut and Elevator 문제 링크 : http://codeforces.com/contest/1084/problem/A 문제 정리어떤 엘레베이터는 작동하지 않을 때는 x 층에서 대기를 한다.엘레베이터는 무조건 한 사람만 태우며, 1층으로 내려가고 다시 x층으로 복귀한다.어떤 사람이 다시 집으로 귀가할 시에 x층에서 1층으로 내려가고 a층까지 작동한 뒤에 x층으로 복귀엘레베이터는 한 층씩 내려갈 때마다 전력 1을 사용n개의 층에 사는 사람들의 수가 주어졌을때, 엘레베이터가 사용할 전력을 최소화 하기위한 x층을 정하라. 문제 풀이 [1... n] 층까지 x 를 정해보면서 전력이 최소일 때를 구한다. 각 층마다 예상 전력 = (층에 사는 사람 수) * ( |x - a| + |a - 1| + |x - 1| ) * ( 2 // 위아래로 ..

티스토리툴바