https://www.acmicpc.net/problem/15738 15738번: 뒤집기 첫째 줄에 배열 A의 크기 N(1 ≤ N ≤ 100,000)과 위치 K(1 ≤ K ≤ N), 연산의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째에는 배열 A에 들어있는 수가 1번째 수부터 순서대로 주어진다. 배열에 들어있는 www.acmicpc.net 각 연산에 따라 기존 k의 위치가 어디로 움직이는지만 확인하여 문제를 해결했다 코드 #include #include #include using namespace std; int n, k, m; int k_point; //k번째에 위치하던 숫자의 현재 위치 int main() { cin.tie(NULL); ios_base::sync_with_stdio(fal..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 배낭 문제와 비슷하게 생각하여, cache[확인하는 앱의 인덱스][확인하는 인덱스의 앱까지 사용된 비용]에 "현재 앱까지 확인하고, 사용된 비용에서 확보할 수 있는 최대 메모리"를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, m; vector ms(105, 0); vector ..

https://www.acmicpc.net/problem/5926 5926번: Cow Lineup Input Details There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1. Output Details The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd. www.acmicpc.net x좌표 순으로 소의 정보를 정렬하고, 투 포인터를 이용해 모든 품종을 포함하는 최소 범위의 x좌표 구간을 구해서 문제를 해결했다. 코드 #..

https://www.acmicpc.net/problem/14907 14907번: 프로젝트 스케줄링 입력은 1줄에서 26줄까지 입력될 수 있으며, 각각은 다른 작업 (위 예제에서 말하자면 A, B, C, …) 을 포함한다. 각 줄에는 다음과 같은 내용이 포함된다. 작업 이름을 나타내는 영문 대문자 하나, www.acmicpc.net 작업의 관계를 그래프로 표현하고 위상정렬과 같은 방법을 통해 탐색해 나아가며, 작업을 시작하려면 해당 작업에 영향을 주는 다른 작업들을 모두 마쳐야 시작이 될 수 있는데, 해당 작업을 시작하는 시간은 해당 작업에 영향을 주는 다른 작업들 중 끝나는 시간이 가장 늦은 작업이 끝나는 시간이라는 것을 이용해서 문제를 해결했다. 코드 #include #include #include ..

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 건물 간의 관계를 그래프로 표현하고, indegree도 저장하여, 건물이 건설되면 해당 건물의 영향을 받아 건설이 될 수 있는 건물의 indegree를 줄이고, 건물이 파괴되면 해당 건물의 영향을 받아 건설이 될 수 있는 건물들의 indegree를 늘려서 정상적으로 건물을 건설하거나 파괴할 수 있는지 판단했다. 이때, 건물들은 중복 건설이 가능하므로 building..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 노드별로 왼쪽 자식 노드의 서브트리의 크기와 오른쪽 자식 노드의 서브트리의 크기를 구하고 이를 이용해 노드별로 어떤 열 번호에 속하는지 구한다. 그리고 루트노드부터 아래로 탐색해 나아가며, 레벨별 속하는 노드들의 열 번호를 저장해 놓고, 이를 통해 각 레벨의 너비를 확인하는 방법으로 문제를 해결했다. 코드 #include #include #include #include using..