https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net vector order에 빙글빙글 도는 순서대로 좌표를 순서대로 넣어놓고 이를 이용하여 문제를 해결했다. 구슬을 다루는 것은 deque를 이용했다. 코드 #include #include #include #include #include using namespace std; int n, m; vector board(50, vector(50, 0)); int dxdy[5][2] = {..

https://www.acmicpc.net/problem/20304 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 로그인 시도에 사용된 비밀번호 값들 에서 bfs를 통해 탐색을 하여 가장 깊은 depth를 구하는 방법으로 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n; int max_bit_size = 0; //비밀번호 최댓값의 비트 자리값 저장 int m; vector p; queue q; v..

https://www.acmicpc.net/problem/2494 2494번: 숫자 맞추기 아래 그림과 같이 N개의 회전이 가능한 숫자 나사가 아래위로 연결되어 있다. 가장 위에 있는 숫자나사는 숫자나사 1이고 가장 아래에 있는 숫자나사는 숫자나사 N이다. 모든 숫자나사는 각각 10 www.acmicpc.net 위에서부터 숫자를 맞춰가며, cache[10000][10]에 [나사 인덱스][이전까지 left 상황]일때 원하는 상태로 만드는데 필요한 최소 회전 칸수를 저장하여 다이나믹 프로그래밍으로 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n; string start; string dest; int ca..

https://www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net visited[1 > k; for (int i = 0; i > input; gold_check[input] = i; } for (int i = 0; i > a >> b >> c; adj[a].push_back(make_pair(c, b)); adj[b].push_bac..

https://www.acmicpc.net/problem/2337 2337번: 트리 자르기 첫째 줄에 n(1≤n≤150), m(1≤m≤n)이 주어진다. 다음 n-1개의 줄에는 트리의 각 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. www.acmicpc.net cache[151][151]에 [루트 정점][트리의 크기] = [루트 정점]이 해당 [트리의 크기]로 되는데 필요한 루트 정점 아래에서 자르는 간선의 개수를 리프 노드부터 bottom-up 방식으로 채워나간다. 이때 주의해야 될 점은 이번에 만들어진 것을 이번에 또 쓰지 않기 위해 큰 값부터 채운다.(for (int j = sub_tree_size[there]; j >= 2; j..

https://www.acmicpc.net/problem/12995 12995번: 트리나라 트리나라는 N개의 도시로 이루어져 있고, 각각의 도시는 1번부터 N번까지 번호가 매겨져 있다. 트리나라의 도로 체계는 트리를 이룬다. 즉, 트리나라에는 N-1개의 양방향도로가 있다. 또, 모두 연 www.acmicpc.net cache[서브트리의 루트번호][마을을 고를 개수]에 경우의 수 (해당 서브트리에서 해당 개수의 마을을 고르는 경우의 수)를 bottom-up 방식으로 채워나가는 방법을 통해 문제를 해결했다. sub_tree_size[there]부터 확인해야 되는데, 작은 것부터 시작하면 이번 순서에 만들어진 것을 이번 순서에 영향을 줄 수 있다(이용할 수 있다) 코드 #include #include #inc..