언젠가 레드코더가 될 남자

[SRM]#739 DIV2

TopCoder · 2018. 10. 11. 11:28

[SRM]#739 DIV2

B. ForumPostMedium풀이단순 시간계산 문제인데, 나에게 stringstream의 아름다움을 느끼게 해준 문제.시간을 전부 초로 바꿔서 계산하면 되는데 문제에서 요구하는 출력을 stringstream을 이용하면굉장히 쉽게 구현 가능하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#includeusing namespace std; class ForumPostMedium{public: string getShownPostTime(string currentTime, string exactPostTime) { stringstream A(currentTime); stringstream B(exactPo..

[BOJ]15810 풍선 공장

BOJ · 2018. 10. 8. 23:17

[BOJ]15810 풍선 공장

문제링크 풀이1이분탐색 소스코드12345678910111213141516171819202122232425262728293031#include #include #include using namespace std; typedef long long ll;int a[1000001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; ll lo = 1LL; ll hi = 1000000000001LL; for (int i = 0; i > a[i]; while (lo + 1 > m; for (int i = 0; i > x; pq.push(make_pair(x,x)); } for (int i = 0; i

[Atcoder]Pyramids & partition

Other Judges · 2018. 10. 6. 23:00

[Atcoder]Pyramids & partition

문제링크C. Pyramids해설입력으로 n줄에 걸쳐서 x,y,h가 주어진다. 피라미드의 중심을 (Cx,Cy), 높이를 H라 할 때,The altitude of coordinates (X,Y) is max(H−|X−CX|−|Y−CY|,0) 의 조건을 주어진 n개의 입력에 대해 모두 만족시키는 피라미드의 중심과 높이를 찾는 문제이다. 풀이피라미드의 중심의 좌표의 제한이 상당히 작은 편이다. 중심의 x좌표, y좌표 모두 0~100 사이 이므로 피라미드의 중심좌표가 가질 수 있는 모든 경우의 수를 다 해보면서 주어진 조건을 만족하는지 확인해보면 된다.소스코드를 보면 아마 이해할 것이다. (좀 지저분하지만..)ans vector는 H의 후보들을 집어넣어두는 곳이고idx vector는 위의 식이 0일때, 그 때의 ..

[SRM]#625 Div2

TopCoder · 2018. 10. 6. 17:49

[SRM]#625 Div2

250. AddMultiply풀이 x has exactly three elements ( x[0] * x[1] ) + x[2] = y Each x[i] must be between -1000 and 1000, inclusive. No x[i] can be equal to 0 or 1. 위의 조건을 만족하는 정수 세 개를 구하는 문제.반복문을 순회하며 조건을 만족하는 세 수가 발견되면 루프를 탈출하면 된다.꼼수(?) 풀이도 가능하다. 소스코드 1(야매)123456789101112131415#include #include #include #include using namespace std; class AddMultiply{public: vector makeExpression(int y){ return {2,..

[SRM] #624 Div2

TopCoder · 2018. 10. 6. 13:19

[SRM] #624 Div2

250. CostOfDancing풀이크기 순으로 정렬 후 k번째 원소까지 더해주면 된다. 12345678910111213141516171819#include #include #include #include using namespace std; class CostOfDancing{public: int minimum(int K, vectordanceCost) { vectorp = danceCost; sort(p.begin(), p.end()); int ans = 0; for (int i = 0; i = 0) costs.push_back(x - y); if (costs.size() >= M) { sort(costs.begin(), costs.end()); int k = 0; for (int i = 0; i

[codeforce] D.Devu and his Brother

Other Judges · 2018. 10. 5. 14:12

[codeforce] D.Devu and his Brother

문제링크 풀이에딧을 보고 푼 문제. 삼분탐색을 잘 몰랐는데 좋은 걸 배웠다.다음에 한번 다시 풀기 위해 기록.주어진 함수가 convex임을 확인한 다음, 3분탐색을 통해 구현. Proof. It is fairly easy to prove. See the derivative of f. = — (# of elements of b > k) + (# of elements of a < k) The first term (without sign) can only decrease as k increases whereas second term can only increase as k increases. So, 소스코드 123456789101112131415161718192021222324252627282930313233..

[SRM] #622 Div2

TopCoder · 2018. 10. 3. 20:07

[SRM] #622 Div2

250. FibonacciDiv2풀이피보나치 수열이 하나 주어진다. (첫항 0, 둘째 항 1)어떤 수가 주어졌을 때, 그 수의 값을 증가시키거나 감소시켜서 피보나치 수열의 구성원소로 만드려고 할 때, 이 때 필요한 연산의 최솟값을 구하는 문제.피보나치 수를 주어진 범위 만큼 전처리 한 다음, 전부 순회해보며 절대값이 작은 값으로 갱신해주면 된다. 소스코드12345678910111213141516171819202122232425262728#include #include using namespace std; int arr[3000000]; class FibonacciDiv2{public: int find(int N) { int mn = 1000000000; arr[0] = 0; arr[1] = 1; int ..

[10476] 좁은 미술전시관

BOJ · 2018. 10. 3. 17:15

[10476] 좁은 미술전시관

문제링크 풀이dp[i][j][k] : i번째 행의 작품을 선택하지 않거나(0), 좌측의 작품을 선택하거나(1), 우측의 작품(2)을 선택하여, 총 k개의 작품을 선택했을 때 만들 수 있는 가치의 최솟값. 최솟값을 구했으니 전체 값에서 빼주면 문제에서 원하는 최대값을 구할 수 있다. 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include #include using namespace std; const int INF = 2e9 + 7; int n, k;int x[202];int y[202]; int dp[202][3][20..

티스토리툴바