#문제 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net #접근방법 dfs를 사용하여 문제에 접근하였다. #풀이 #include #include using namespace std; vector v[105]; int virus[105]; int ans; void dfs(int x){ for(int i=0;i
#문제 2579번: 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net #접근방법 동적계획법으로 접근하였다. #풀이 #include #include using namespace std; int arr[305]; int dp[305]; int main(){ int n; scanf("%d",&n); for(int i=0;i
#문제 17626번: Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net #접근방법 동적계획법을 사용하여 접근하였다. #풀이 #include #include using namespace std; int dp[50005]; int main(){ int n; scanf("%d",&n); for(int i=1;i
#문제 17219번: 비밀번호 찾기 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net #접근방법 map이라는 자료구조를 사용하면 쉽게 풀 수 있다. #풀이 #include #include using namespace std; int main(){ cin.tie(NULL); ios::sync_with_stdio(false); int N,M; map m; string a,b; cin >> N >> M; for(int i..
#문제 11399번: ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net #접근방법 정렬을 하고 반복문을 돌면서 시간의 합을 구하면 된다. #풀이 #include #include using namespace std; int arr[1005]; int main(){ int n; int ans = 0; scanf("%d",&n); for(int i=0;i
#문제 11047번: 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net #접근방법 가장 높은 가치를 가진 동전부터 몇 개가 필요한지 구하면 되는 그리드 알고리즘을 사용하였다. #풀이 #include int arr[10]; int main(){ int n,k,ans = 0; int sum = 0; scanf("%d %d",&n,&k); for(int i=0;i=1;i--){ ..
#문제 1764번: 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net #접근방법 map 자료구조를 사용하면 쉽게 풀 수 있다. #풀이 #include #include #include #include using namespace std; int main(){ int N,M,cnt=0; string s; map m; map::iterator iter; scanf("%d %d",&N,&M); for(int i=0;i> s; m[s]++; if..
#문제 11723번: 집합 https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net #접근방법 비스마스크 기법을 사용하는 문제이다. 하지만 범위가 1~20 이라서 그냥 배열로 풀어도 메모리 제한은 걸리지 않는다. #풀이 #include #include char a[10]; int main(){ int M,x; int s = 0; scanf("%d",&M); while(M--){ scanf("%s",a); if(strcmp(a,"all")==0){ s = (1
#문제 1676번: 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net #접근방법 N!은 1부터 N까지의 숫자의 곱을 의미한다. N!의 0의 개수를 구하려면 10의 약수인 2와 5의 개수를 먼저 구해줘야한다. #풀이 #include int main(){ int n; int a=0,b=0; int ans; scanf("%d",&n); for(int i=2;i
