출항사

C가 왤캐 복잡한 빡구현이 나온지 모르겠지만, 망했다 ㅠ 너무 풀기 싫게 생겼다. 근데 저번 305때는 4솔이였는데 그때보다 등수가 더 높다. C가 좀 어렵긴 했나보다. E도 하필 조합론이 나왔고, 좀 나랑 안맞았던 셋 같다. 그래도 업솔빙 하면서 조합론을 연습해봐야 할것 같다. 문제가 너무 코드포스 같았다 A - 3:40 7개씩 숫자를 묶어서 더한 후 출력하면 된다. #include #include #include #include #include #include #include #include #define X first #define Y second #define NUM 200010 using namespace std; typedef pair pii; typedef long long ll; int a..

DP로 해결할 수 있는 문제이다. 각 음식은 0과 1로 주어지는데, 연속해서 1을 먹을 수가 없다고 한다. 그리고 음식을 먹지 않고 skip을 할 수도 있다. 1을 먹은 상태에서 0을 먹으면 상태가 0으로 변한다. 그래서 직관적으로 0인 음식은 무조건 먹으면 되겠네.. 싶지만 음수가 주어질 수도 있다. 따라서 최근 먹은 음식이 0인지 1인지의 경우의 수로 나누고 점화식을 세워볼 수 있다. DP[i][j] = i 상태이고 j번째 음식까지 먹었을때의 최댓값으로 설정하자. 그다음 각 음식의 상태에 따라 점화식을 2개 만들 수 있는데, 현재 음식이 0인 경우와 1인 경우로 나눠보자. 현재 i번째 음식이 0이라면, DP[0][i-1], DP[1][i-1] 중 최댓값과 현재 음식의 만족도를 더한 값을 DP[0][i..

간단한 정렬 문제이다. N이 주어지고 3 * N개의 입력으로 숫자들이 입력된다. 이때 i (1 N; for (int i=0; i> x; cnt[x]++; if (cnt[x] == 2) { v.push_back({x, i}); } } sort(v.begin(), v.end(), compare); for (auto curr : v) { cout

set 자료구조를 잘 써야 하는 문제이다. N개의 노드가 존재하고, 초기 상태는 어떠한 간선도 존재하지 않는다. 그리고 이제부터 Q개의 쿼리를 입력받게 된다. 쿼리의 개수는 2개인데, 1번 쿼리의 경우 간선을 연결하고 2번 쿼리의 경우 특정 노드와 연결된 모든 간선을 끊는 연산을 수행해야 한다. 각 쿼리를 수행할때 마다 어떠한 노드와도 연결되지 않은 노드의 개수를 출력해야 한다. N, Q > n >> m; int answer = n; for (int i=0; i> x; if (x == 1) { cin >> y >> z; if (v[y].size() == 0) { answer--; } if (v[z].size() == 0 ) { answer--; } v[y].insert(z); v[z].insert(y);..

A배열에 N개의 선물이 들어오고, B 배열에 M개의 선물이 들어온다고 한다. 우리가 구하고 싶은 값은 A배열과 B배열에서 임의로 선물을 하나씩 선택했을때, abs(A - B) > n >> m >> d; for (int i=0; i> x; A.push_back(x); } for (int i=0; i> x; B.push_back(x); } sort(A.begin(), A.end()); sort(B.begin(), B.end()); for (int i=0; i

약간의 테크닉이 필요한 그래프 탐색 문제였다. 그래프가 주어지고, K개의 특별한 노드가 주어진다. 이 특별한 노드는 가드가 존재하는데, 이 가드는 자신과의 거리가 h 미만인 노드들을 지킬 수 있다는 상황이 주어진다. 이때 가드에 의해 보호받을 수 있는 노드의 총 개수와 번호를 출력해야 하는 문제이다. 그래서 나는 다익스트라로 문제를 접근했다. 가드가 지키고 있는 노드들을 전부 우선순위 큐에 때려박고, 순차적으로 탐색을 할 것이다. 이때 우선순위 큐에서 꺼내는 정렬 기준은 '남은 h의 크기'로 잡았다. 왜냐하면 초기 K에 속하지 않는 어떤 P라는 노드가 있다고 가정해보자. 이 P라는 노드에 도달할 수 있는 방법은 여러가지가 존재할 수도 있는데, 우리는 이 P라는 노드에 도달할 수 있으면서 h가 가장 크게 ..

음.. C에서 조금 말려가지고 아쉽다. D도 조금 해매고.. E는 조금 신박했는데 왜 안뚫리는지 모르겠다. 그래도 문제는 전반적으로 재밌었던 것 같다. A - 4:32 N이 주어질때, 가장 가까운 5의 배수 숫자를 찾으면 된다. #include #include #include #include #include #include #define MINF 0x7f7f7f7f #define INF 300000000000001 #define MOD 10007 #define NUM 200010 #define X first #define Y second using namespace std; typedef long long ll; typedef pair pii; typedef pair pdd; typedef pair pi..

D - A Piece of Cake AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 당시에는 풀지 못했지만 좀 간단하게 생각해보면 어렵지 않은 문제이다. 딸기의 위치가 2차원 격자로 주어지고, 이 2차원 격자를 A개의 row, B개의 column으로 자르려고 한다. 그러면 (A+1) * (B+1)개의 공간이 생기게 되는데, 여기서 발생한 공간 중 딸기가 존재하는 최소 영역과 최대 영역을 구하면 되는 문제이다. 좌표의 크기가 매우 크기 때문에 좌표 압축이 필요하다는 것을 알 수 있고, 이 좌표 압축 기법을 활용하면 별도의 ..