[C++] Virus (바이러스) (BAEKJOON 2606)

/*

https://www.acmicpc.net/problem/2606

I used BFS strategy.

*/


#include <iostream>
#include <queue>

using namespace std;

int num, num_matrix;
int con[101][101];
int flags[101];

queue<int> que;

int bfs(int start);

int main() {
cin >> num;
cin >> num_matrix;

for (int i = 0; i<num_matrix; i++) {
int x, y;

cin >> x;
cin >> y;

con[x][y] = 1;
con[y][x] = 1;
}

cout << bfs(1) << endl;
return 0;
}

int bfs(int start) {
int count = 0;
int now;

que.push(start);
flags[1] = 1;

while (!que.empty()) {
now = que.front();
que.pop();

for (int i = 1; i <= num; i++) {
if ((con[now][i] == 1) && (flags[i] != 1)) {
que.push(i);
flags[i] = 1;
count++;
}
}
}

return count;
}

[C++] Sugar Delivery (설탕 배달) (BAEKJOON 2839)

/*
https://www.acmicpc.net/problem/2839

The idea is, we have to use 5KG bag as mush as possible.
so start with the maximum number of 5KG bags, repeat checking and reducing the number of 5KG bags.



*/



#include <iostream>

using namespace std;

int main(){
int n;
int kg5=0,kg3=0;
int rem=0,answer=0;
 
cin >> n;

if((n<3)||(n>5000)){
answer = -1;
cout << answer;
return 0;
}

if(n%5 == 0){ //If n is a multiple of 5, get the answer quickly
answer = n/5;
cout << answer;
return 0;
}

for(kg5 = n/5; kg5 >=0; kg5--){
rem = n - (kg5*5); //exclude an amount of 5kg sugar

if(rem%3 == 0){ //check its remainder is 0
kg3 = rem/3;
break; //we got the answer. go out.
}

//reduce kg5 and repeat.
}

//If this loop couldn't get the answer, then kg5 must be -1, kg3 must be 0. In the case, kg5 + kg3 is -1.

answer = kg5 + kg3;
cout << answer;

return 0;
 
}

[C++] Fast multiply algorythm (BAEKJOON 1629)

Algorithm Quiz

백준 1629 "Multiply"

https://www.acmicpc.net/problem/1629

Get A^B

But the number could be too huge, so devide it by c and get the remainder.

so, get A^B%C

/////////////////////////////////////////////////////////////////////////////////////////////////////

We can solve it with Divide And Conquer.

Use long long type because the number can be a big number.

/* Wrong answer. It could happen overflow. */

#include <iostream>

#include <Windows.h>

using namespace std;

long long a, b, c;

long long calc(long long a, long long b, long long c)

{

if (b == 0) { return 1; }

else if (b == 1) { return a%c; }

else if (b % 2 == 0) { return calc(a*a, b >> 1, c) % c; }

else { return a * calc(a, b - 1, c) % c; }

}

int main() {

cin >> a >> b >> c;

cout << calc(a, b, c) << '\n';

system("pause");

return 0;

} 

/* Correct answer */

#include <iostream>

using namespace std;

long long a, b, c;

long long calc(long long a, long long b, long long c)

{

if (b == 0) {return 1;}

else if(b == 1) {return a%c;}

else if (b % 2 == 0) {long long temp = calc(a, b/2, c); return (temp*temp)%c;}

else {return a * calc(a, b-1, c) % c;}

}

int main() {

cin >> a >> b>> c;

cout << calc(a, b, c) << '\n';

return 0;

}

//
Reference
C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1629번:곱셈 답
http://codecollector.tistory.com/m/268