알고리즘/BOJ
백준 4641번: Doubles
대 혁
2020. 5. 6. 19:15
4641번: Doubles
문제 2~15개의 서로 다른 자연수로 이루어진 리스트가 있을 때, 이들 중 리스트 안에 자신의 정확히 2배인 수가 있는 수의 개수를 구하여라. 예를 들어, 리스트가 "1 4 3 2 9 7 18 22"라면 2가 1의 2배, 4가 2의 2배, 18이 9의 2배이므로 답은 3이다. 입력 입력은 여러 개의 테스트 케이스로 주어져 있으며, 입력의 끝에는 -1이 하나 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 2~15개의 서로 다른 자연수가 주어진다.
www.acmicpc.net
입력받은 숫자들을 전부 vector에 담아 2중 for문을 돌려도 정답은 쉽게 찾을 수 있겠지만, 효율성을 늘리기 위해 하나의 for문을 사용하는 쪽으로 구현하였다.
자연수의 최대값이 100을 넘지 않기 때문에 계수정렬을 이용하였고, for_each 함수를 사용하여 벡터에 담긴 모든 원소를 탐색하였다.
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int numberCnt[101], result;
void Pred(const int a)
{
result += numberCnt[a*2];
}
int main(void)
{
vector<int> v;
while (1)
{
result = 0;
memset(numberCnt, 0, sizeof(numberCnt));
while (1)
{
int num;
cin >> num;
if (num == -1) return 0;
else if (num == 0) break;
v.push_back(num);
numberCnt[num]++;
}
for_each(v.begin(), v.end(), Pred);
v.clear();
cout << result << endl;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 32day