소심야채

문제: https://www.acmicpc.net/problem/17610 17610번: 양팔저울 무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 www.acmicpc.net 문제해석: 위 그림과 같이 왼쪽 저울에 물을 담기위한 빈그릇을 고정한다고 가정해보자. 자 우리는 한개의 추를 가지고 3가지 행동을 할수있다. 1. 추를 오른쪽에 올린다 :: 이 경우 빈그릇에 무게는 추의 무게만큼 증가한다. 2. 추를 왼쪽에 올린다 :: 이 경우 빈그릇에 무게는 추의 무게만큼 감소한다. 3. 추를 어느저울에도 올리지 않는다 :: 이 경우 빈그릇에 무게의 변화가 없다. 추의..

문제: https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제해석: 회문(回文) 또는 팰린드롬(palindrome)은 앞에서 읽으나 거꾸로 읽으나 같은 문장을 뜻한다 ex) level, 다시합시다 이 문제의 특징은 회문은 아니지만 한 글자를 삭제하면 회문이되는 "유사회문" 이라는 상태가있다는 것이다. 따라서 입력으로 주어진 문자열은 총 3가지 상태로 표현할수있다. 0 : 회문 1 : 유사회문 2 : 회문X 유사회문X 각 상태를 나타내는 숫자의 특징은 회문을 만들기 위해 삭제해..

문제: https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net 문제 해석: 위 그림과 같이 n번선분부터 시작해 1번 선분까지 보면서 --> for(int i=n; i>=1; i--) 현재의 최대 높이(maxH) 보다 높은 선분(i번선분)을 발견했을때 최대높이를 갱신함과 동시에 답의 갯수증가를 해준다. 여기서 n번 선분이 시작 당시에 최대높이인것이 자명함으로 최대높이를 n번선분으로 초기화, 답의 갯수를 1로 초기화 후에 [n-1...1]번 선분을 보는 방법이..

#include using namespace std; const int treeSize = 1>=1){ if(l&1){ maxV = max(maxV,maxTree[l]); minV = min(minV,minTree[l++]); } if(!(r&1)){ maxV = max(maxV,maxTree[r]); minV = min(minV,minTree[r--]); } } return (maxV - minV) > t >> n; fill(minTree, minTree + treeSize*2, INT_MAX); for(int i=0; i> minTree[treeSize + i]; maxTree[treeSize + i] = minTree[treeSize + i]; } for(int i = treeSize-1; i>0;..

#include #include #include #include using namespace std; typedef long long LL; const int MAX_N = 100010; int sqrtN; struct Query { int idx, s, e; bool operator < (Query &x) { if (s / sqrtN != x.s / sqrtN) return s / sqrtN < x.s / sqrtN; return e < x.e; } }; vector query; int arr[MAX_N], cnt[MAX_N*10]; LL ret = 0, ans[MAX_N]; void add(int x) { ret += (LL)(2 * ++cnt[x] - 1)*x; } void sub(int x) { ..

전형적인 knapsack problem 문제이다. #include #include #include #include using namespace std; typedef pair pii; const int MAX_N = 100; const int MAX_T = 10010; int cache[MAX_N][MAX_T]; int n, t; pii test[MAX_N]; //{studyTime, score} int solve(int idx, int time) // idx단원 이후에 얻을수있는 최대점수 { if (idx == n) return 0; int& ret = cache[idx][time]; if (ret != -1) return ret; ret = solve(idx + 1, time); // idx단원 공부..

#include #include #include using namespace std; const int MAX_N = 100 + 5; const int MAX_W = 100100; int main() { int N, K; int W[100100]; int dp[MAX_N][MAX_W]; // dp[i][j] = [0...i]번 배낭을 사용하여 총합무게 j일때 얻을 수 있는 가치의 최댓값 int weight[MAX_N], value[MAX_N]; scanf("%d %d", &N, &K); for (int i = 1; i

https://www.acmicpc.net/problem/10165 [문제조건] 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000), 버스 노선의 수 M(2 ≤ M ≤ 500,000) 각 버스의 노선 [a,b] 단, 0 ≤ a,b ≤ N-1이고 a ≠ b [문제풀이] 조건 a ≠ b 로 인하여 각 버스의 노선 [a,b]를 두 분류로 나눌수가 있다. $$\displaystyle \begin{cases}ab & passZeroZone\end{cases}$$ ZeroZone == [n-1,0] 그룹 A의 특징으로는 (n-1)번과 0번사이 도로를 지나가지 않으며, 그룹 B의 특징으로는 (n-1)번과 0번사이 도로를 무조건 지나간다. 따라서 그룹A는 그룹 B를 포함할수 없는점을 알수가 있으며, 그룹 ..