목록PS/알고리즘 문제풀이 (157)
득이공간
[백준 C++] 7576 토마토 - 너비우선탐색
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net #include #include #include using namespace std; vector Box; queue Queue1; queue Queue2; int BFS(int N, int M) { int Day = 0; while (true) { while (!Queue1.empty()) { int Row = Queue1.front().first; int Col = Queue1.front().second; Queue1.pop(); // Lef..
[백준 C++] 11724 연결 요소의 개수 - 깊이우선탐색
11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net #include #include #include using namespace std; vector Neighbors; vector Visited; void DFS(int Node) { Visited[Node] = true; for (const int& Neighbor : Neighbors[Node]) { if (Visited[Neighbor]) { continue; } DFS(Neighbor); } ..
[백준 C++] 1012 유기농 배추 - 깊이우선탐색
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #include #include #include using namespace std; int Map[50][50]; list Neighbors[50][50]; void DFS(int Row, int Col) { Map[Row][Col] = 0; for (const pair& Neighbor : Neighbors[Row][Col]) { if (Map[Neighbor.first][Neighbor.second] == 0) { continue; } DFS(Neighbor.first..
[백준 C++] 1715 카드 정렬하기 - 그리디
1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net #include #include #include using namespace std; priority_queue Cards; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 0; i > Card; Cards.emplace(Card); } int Cnt = 0; for..
[백준 C++] 13305 주유소 - 그리디
13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net #include #include using namespace std; vector City; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; City.reserve(N); for (int i = 0; i > Distance; } City.empla..
[백준 C++] 1541 잃어버린 괄호 - 그리디
1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string Input; getline(cin, Input); // Split Two Set int SubtractIndex = Input.find('-'); string SumString = Input.substr(0, SubtractInde..
[백준 C++] 11726 2xn 타일링 - 다이나믹프로그래밍
11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net #include using namespace std; int DP[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; DP[1] = 1; DP[2] = 2; for (int i = 3; i
[백준 C++] 9095 1, 2, 3 더하기 - 다이나믹프로그래밍
9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #include using namespace std; int DP[11]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); DP[0] = 0; DP[1] = 1; DP[2] = 2; DP[3] = 4; for (int i = 4; i > T; for (int i = 0; i > Number; cout
[백준 C++] 1003 피보나치 함수 - 다이나믹프로그래밍
1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net #include using namespace std; pair DP[41]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); DP[0] = make_pair(1, 0); DP[1] = make_pair(0, 1); for (int i = 2; i > T..
[백준 C++] 11659 구간 합 구하기 4 - 자료구조
11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net #include #include using namespace std; vector Sum; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; Sum.reserve(N); for (int i = 0; i > Number; if (i == 0) { Sum.emplace_..