์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- java
- ์ฐ์ ์์ ํ
- DP
- OS
- ๋ถํ ์ ๋ณต
- GCP
- ๋์ ํฉ
- ์๋ฎฌ๋ ์ด์
- dynamic debugging
- ๋ฐฑํธ๋ํน
- CVE
- c++
- dfs
- error
- BFS
- ๊ตฌํ
- ์ด๋ถ ํ์
- ์ฌ๊ท
- Reversing
- ๋ฌธ์์ด
- ์์ ์ ๋ ฌ
- ๋งต
- ๊ทธ๋ฆฌ๋
- ๋ฐ์ดํฌ์คํธ๋ผ
- thymeleaf
- ์ต๋จ ๊ฒฝ๋ก
- JPA
- web
- ์คํ
- Spring
- Today
- Total
hades
[Baekjoon] 2143๋ฒ: ๋ ๋ฐฐ์ด์ ํฉ ๋ณธ๋ฌธ
๐ฅ ๋ฌธ์
https://www.acmicpc.net/problem/2143
๐ ์ค๊ณ
๋ถ๋ฐฐ์ด์ ํํ๋ฅผ ๋ณด๋ฉด, ๋์ ํฉ์ ์ด์ฉํด์ผ ํ๋ค๋ ๊ฒ์ ์ฝ๊ฒ ํ์ ํ ์ ์๋ค.
์ฒ์์๋ A์ B์ ๋ถ๋ฐฐ์ด์ ๊ตฌํด์ ์๋ก ๋ค๋ฅธ ๋งต์ ์ ์ฅํ ํ, ํ ์ชฝ์์ ๋ฐ๋ณต์๋ฅผ ์ฌ์ฉํด ๋ฐ๋ณตํ๋ฉด์, (T - ํ ์ชฝ์ ์๋ ๋ถ๋ฐฐ์ด์ ํฉ)์ด ๋ค๋ฅธ ์ชฝ์ ์์ผ๋ฉด, (ํ ์ชฝ์ ์๋ ๋ถ๋ฐฐ์ด์ ํฉ์ ๊ฐ์) * (๋ค๋ฅธ ์ชฝ์ ์๋ ๋ถ๋ฐฐ์ด์ ํฉ์ ๊ฐ์)๋ก ๊ตฌํ๋ ค๊ณ ํ์ผ๋ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฐ์ํ์๋ค. ๋งต ํ๋๊ฐ ์ต๋ 1000000๊ฐ * 2 * 4Bytes ์ด๋ฏ๋ก 64MB๋ฅผ ์ด๊ณผํ๊ธฐ ๋๋ฌธ์ด์๋ค.
๊ทธ๋์, ๋งต์ ํ๋๋ง ๋ง๋ค๊ณ , ๋ค๋ฅธ ์ชฝ์์ ๋ถ๋ฐฐ์ด์ ํฉ์ ๋ง๋ค๋ฉด์ ๋ฐ๋ก ์ฐพ๋ ๋ฐฉ์์ ์ฌ์ฉํ์๋ค. ๋ถ๋ฐฐ์ด์ ํฉ์ ๋ง๋ค๊ธฐ ์ํด ์ด์ค ๋ฐ๋ณต๋ฌธ์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ 1000000, ํ ์ชฝ์์ T - (๋ง๋ ๋ถ๋ฐฐ์ด์ ํฉ)์ ์ฐพ๊ธฐ ์ํด log1000 ์ด๋ฏ๋ก 10^7์ด๊ธฐ ๋๋ฌธ์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ์ง ์๋๋ค.
์์ ๋ง์ฐฌ๊ฐ์ง๋ก, ํ ์ชฝ์์ ๋ถ๋ฐฐ์ด์ ํฉ์ ๋ง๋ค๊ณ , ๋ค๋ฅธ ์ชฝ์ T - ๋ถ๋ฐฐ์ด์ ํฉ์ด ๋ช ๊ฐ๊ฐ ์๋์ง ๊ตฌํด์ ๊ฒฐ๊ณผ์ ๋ํ๋ฉด ๋๋ค. ๊ทธ ๊ฐ์๋ lower_bound์ upper_bound๋ฅผ ์ด์ฉํ์ฌ ์ ๋ฐฉ๋ฒ๋ณด๋ค ๋น ๋ฅด๊ฒ, ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ ๊ฒ ์ฌ์ฉํ์ฌ ๊ตฌํ ์ ์๋ค.
upper_bound๋ key๋ณด๋ค ํฐ ์ต์ด์ ์์น๋ฅผ ๋ฐํํ๊ณ , lower_bound๋ key๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ์ต์ด์ ์์น๋ฅผ ๋ฐํํ๋ค. upper_bound - lower_bound๋ ๋ฐฐ์ด์์ key์ ๊ฐ์๊ฐ ๋๋ค๋ ๊ฒ์ ์ด์ฉํ๋ค.
๐ ํ์ด
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int t, n, m;
vector<int> a(1000);
vector<int> aSum(1000);
vector<int> b(1000);
vector<int> bSum(1000);
map<int, int> aMap;
long long result = 0;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i > 0) {
aSum[i] = a[i] + aSum[i - 1];
}
else {
aSum[i] = a[i];
}
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> b[i];
if (i > 0) {
bSum[i] = b[i] + bSum[i - 1];
}
else {
bSum[i] = b[i];
}
}
for (int i = 0; i < n; i++) {
if (aMap.find(aSum[i]) != aMap.end()) {
aMap[aSum[i]] += 1;
}
else {
aMap.insert({ aSum[i] , 1 });
}
for (int j = 0; j < i; j++) {
long long part_sum = aSum[i] - aSum[j];
if (aMap.find(aSum[i] - aSum[j]) != aMap.end()) {
aMap[part_sum] += 1;
}
else {
aMap.insert({ part_sum, 1 });
}
}
}
for (int i = 0; i < m; i++) {
if (aMap.find(t - bSum[i]) != aMap.end()) {
result += aMap[t - bSum[i]];
}
for (int j = 0; j < i; j++) {
long long part_sum = bSum[i] - bSum[j];
if (aMap.find(t - part_sum) != aMap.end()) {
result += aMap[t - part_sum];
}
}
}
cout << result << "\n";
return 0;
}
๐ ํ์ด2
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int t, n, m, part_sum;
vector<int> a(1000);
vector<int> aSum(1000);
vector<int> b(1000);
vector<int> bSum(1000);
vector<int> partSumA;
long long result = 0;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i > 0) {
aSum[i] = a[i] + aSum[i - 1];
}
else {
aSum[i] = a[i];
}
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> b[i];
if (i > 0) {
bSum[i] = b[i] + bSum[i - 1];
}
else {
bSum[i] = b[i];
}
}
for (int i = 0; i < n; i++) {
partSumA.push_back(aSum[i]);
for (int j = 0; j < i; j++) {
partSumA.push_back(aSum[i] - aSum[j]);
}
}
sort(partSumA.begin(), partSumA.end());
for (int i = 0; i < m; i++) {
result += upper_bound(partSumA.begin(), partSumA.end(), t - bSum[i]) -lower_bound(partSumA.begin(), partSumA.end(), t - bSum[i]);
for (int j = 0; j < i; j++) {
part_sum = bSum[i] - bSum[j];
result += upper_bound(partSumA.begin(), partSumA.end(), t - part_sum) - lower_bound(partSumA.begin(), partSumA.end(), t - part_sum);
}
}
cout << result << "\n";
return 0;
}
๐ ๋ฉ๋ชจ
์ฒซ ์ธ๋ฑ์ค๋ถํฐ ์ด๋ ์ธ๋ฑ์ค๊น์ง์ ๋ถ๋ถํฉ์ ๋ฃ๋ ๊ณผ์ ์์ ๊ทธ ๊ฐ์ด ์ด๋ฏธ ์กด์ฌํ ์ ์๋ค.
'๐ PS > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 1138๋ฒ: ํ ์ค๋ก ์๊ธฐ (0) | 2024.09.25 |
---|---|
[Baekjoon] 2252๋ฒ: ์ค์ธ์ฐ๊ธฐ (0) | 2024.09.23 |
[Baekjoon] 1202๋ฒ: ๋ณด์ ๋๋ (0) | 2024.09.19 |
[Baekjoon] 9527๋ฒ: 1์ ๊ฐ์ ์ธ๊ธฐ (0) | 2024.09.18 |
[Baekjoon] 1562๋ฒ: ๊ณ๋จ ์ (0) | 2024.09.16 |