#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector<vector<pair<int, int>>> v;
vector<bool> visited;
int result;
void CheckLink(int k, int from)
{
result++; //탐색마다 1씩 증가 시켜줍니다.
visited[from] = true; //같은 인덱스 탐색을 막아줍니다.
int size = v[from].size();
for (int i = 0; i < size; ++i)
{
pair<int, int> p = v[from][i];
int next = p.first;
int cost = p.second;
//이미 방문 되었거나 k보다 작은 곳은 갈 수 없습니다.
if (visited[next] || cost < k)
{
continue;
}
//계속 탐색합니다.
CheckLink(k, next);
}
}
int main()
{
int n, Q;
int p, q, r;
int k, from;
scanf("%d %d", &n, &Q);
v.resize(n + 1); //인덱스가 [1] ~ [n] 까지 시작하여 n + 1 만큼 사용합니다.
visited.resize(n + 1, false);
for (int i = 1; i < n; ++i) //n - 1개 입력이기에 i = 1부터 시작합니다.
{
scanf("%d %d %d", &p, &q, &r);
//양방향 그래프이기에 서로 경로, 가중치 를 저장해줍니다.
v[p].push_back(make_pair(q, r));
v[q].push_back(make_pair(p, r));
}
for (int i = 0; i < Q; ++i)
{
scanf("%d %d", &k, &from);
result = -1;
//visited 배열을 false로 초기화 시켜줍니다.
fill(visited.begin(), visited.end(), false);
//DFS
CheckLink(k, from);
printf("%d\n", result);
}
}
(이분 탐색이 left <= right, left < right 등과 같이 여러 변형이 있고 쓰이는 곳이 달라집니다.
이건 종이에 써가면서 해보는게 좋을거 같네요!)
#include <iostream>
#include <algorithm>
using namespace std;
int input[1000000];
int BinarySearch(int n, int m)
{
int left = 0;
int right = 1000000000;
while (left <= right)
{
int mid = (left + right) / 2;
long long sum = 0LL;
for (int i = 0; i < n; ++i)
{
if (input[i] > mid)
{
sum += (long long)input[i] - (long long)mid;
}
}
if (sum == m)
{
return mid;
}
else if (sum > m)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return right;
}
int main()
{
int n, m;
int left = 0;
int right = 0;
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
cin >> input[i];
}
sort(input, input + n);
cout << BinarySearch(n, m) << endl;
}
다른 방법은 높이를 큰 순서로 나열한 후 잘라가며 원하는 수량을 체크하는 것입니다.
이 방법은 제가 알아낸 것은 아니고 어떤 분의 풀이였던 것 같습니다.
1
2
#include <iostream>
#include <algorithm>
using namespace std;
int input[1000001];
bool compare(int a, int b)
{
return a > b;
}
int main()
{
int n, m;
long long sum = 0;
int index = 1;
int cut = 0;
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
cin >> input[i];
}
sort(input, input + n, compare);
while (sum < m)
{
sum += ( (long long)input[index - 1] - (long long)input[index] ) * index;
index++;
}
cut = (sum - m) / (index - 1);
cout << input[index - 1] + cut << endl;
}
cut을 구하는 것이 핵심인 코드입니다. ㅎㅎ
(이때 index가 배열의 크기를 넘어서지 않기위해 n + 1개 만큼의 배열로 선언해주어야 합니당.)
(대신 인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해주어야 한다.)
아래의 그림을 확인해보자. 뭔가 떠오르지 않을까!
위의 초록 경계 구역을 걸러낼 수 있게된다. 저 부분은 미리 더해주고 복잡하니깐 없는 것으로 취급해도 된다.
(인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해주어야 한다.)
row = 2로 4 x 4의 구역에 들어간다. 이전 구역 2 x 2 부분은 2번 넘어왔다는 것을 알 수 있다.
col = 2로 4 x 4의 구역에 들어간다. 이전 구역 2 x 2 부분을 1번 넘어왔다.
즉 위의
row와 col 은 4 x 4 로 4의 경계에 있기 때문에
4 / 2 = 2 가 이전 경계가 된다.
(row 2개 구역) + (col 1개 구역)
( 2 x 2 x 2 ) + ( 2 x 2 )
를 계산해주고 치워버려도 된다.
어차피 패턴은 똑같기 때문이다. 남는 것은 아래와 같다.
남기기 위해 row와 col 값을 변경해준다. 계산이 끝난 부분은 필요 없기 때문이다.
row : 미리 계산 된 곳은 빼준다. row = row(2) - 2^2 / 2 = 0
col : 미리 계산 된 곳은 빼준다. col = col(2) - 2^2 / 2 = 0
row = 0, col = 0 으로 이제 위의 입장에 봤을 때 0, 0이 정답이다. (원래는 12가 정답)
만약에 남은 인덱스가 0, 0 이 아니라 2, 4 등의 다른 숫자가 나오면 해당 부분도 계속 2의 제곱 수로
경계를 걸러주며 갯수는 결과에 더해주고, 해당 구역은 제거해 주면서 반복하면 된다.
중요한 것은
(row, col 인덱스가 0부터 시작하기 때문에 r == 2^x 인 경우도 경계를 넘는것으로 인정해준다.)
row가 경계를 넘게 되면 2개의 구역을 넘게 된다. 2개의 구역에 대해 더해주기.
col은 왼편의 1개의 구역만을 넘기때문에 1개의 구역에 대해서만 더해주면 된다.
#include <iostream>
using namespace std;
int main()
{
int n, r, c;
int result = 0;
cin >> n >> r >> c;
while (r > 0)
{
int size = 2;
while (size <= r)
{
size *= 2;
}
size /= 2;
result += size * size * 2;
r -= size;
}
while (c > 0)
{
int size = 2;
while (size <= c)
{
size *= 2;
}
size /= 2;
result += size * size;
c -= size;
}
cout << result << endl;
}
2. Ascending (오름차순 ex: 1 2 3 4) , Descending (내림차순 ex: 4 3 2 1)이 반복되는 형태로 되어있다.
2번 규칙 순서가 바뀌는 것을 제외하고 1번 규칙만을 놓고 나열을 해보면 아래와 같이 숫자가 나열 된다.
1/1
1/2 2/1
1/3 2/2 3/1
1/4 2/3 3/2 4/1
잘 보면
X / 최대 숫자
X + 1 / 최대 숫자 - 1
...
이런식으로 흘러가는 걸 알 수 있다.
이걸 이용해서
X - 최대 숫자 > 0 이면
X = X - 최대숫자, 최대숫자 증가
X - 최대 숫자 <= 0 이면
오름차순 or 내림차순 순서에 따라 X / 최대 숫자 - X + 1 또는 최대 숫자 - X + 1 / X
를 출력해주기만 하면 된다. (이렇게 작성함)
#include <iostream>
using namespace std;
int main()
{
int x;
int num = 1;
bool isAscending = true;
cin >> x;
while (true)
{
isAscending = !isAscending;
if (x - num <= 0)
{
if (isAscending)
{
cout << x << "/" << num - x + 1 << endl;
}
else
{
cout << num - x + 1 << "/" << x << endl;
}
break;
}
x -= num;
num++;
}
}
