https://www.acmicpc.net/problem/2543 2543번: 초고속철도 첫째 줄에 문제의 조건을 만족하면서 처리장치를 부착할 수 있는 경우의 수를 출력한다. 만약 경우의 수가 20,070,713 이상일 때에는 20,070,713으로 나눈 나머지를 출력한다. 또한 계산 도중 오버플 www.acmicpc.net cache[index]에 'index번째 로봇부터 고려하여 구하는 처리장치 부착 경우의 수' 를 저장하여 다이나믹 프로그래밍(DP)을 이용해 문제를 해결했다. index번째 로봇부터 고려하는 처리장치 부착 경우의 수는 index번째에 처리 장치를 부착하는 경우와 부착하지 않는 경우로 나누어서 경우의 수를 고려했으며, index번째에 처리 장치를 부착하지 않는 경우에는 index번째 ..

https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하 www.acmicpc.net BFS를 통해 갈 수 있는 땅의 개수를 확인하는데, 탐색할 위치를 확인할 때, 이전에 확인할 때 보다 왼쪽으로 움직일 수 있는 횟수 또는 오른쪽으로 움직일 수 있는 횟수가 큰 경우일 때만 큐에 넣어서 탐색을 진행하도록 하여 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, m; int l, r; vector boar..

https://www.acmicpc.net/problem/16468 16468번: 크리스마스 트리 꾸미기 이진트리란 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조로, 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드가 있다. 제일 위에 노드가 1개, 그 다음 2개… 와 같은 식으로 위에 www.acmicpc.net cache[트리높이][볼 개수]에 해당 트리높이에서 해당 볼 개수를 가지고 있을 때 만들어질 수 있는 트리의 경우의 수를 저장하는 방법으로, 트리에서 다이나믹 프로그래밍(트리 DP)을 이용해 문제를 해결했다. height높이의 트리를 ball_cnt개의 공으로 만드는 경우의 수를 구할때, 왼쪽 자식의 트리 또는 오른쪽 자식의 트리 중 최소 하나는 height - 1 높이의 트리를 ..

https://www.acmicpc.net/problem/1184 1184번: 귀농 상근이와 선영이는 도심 속의 삶에 싫증을 느꼈고, 친구 현수가 있는 시골로 농사를 지으려 내려왔다. 현수의 땅은 크기가 N×N 인 정사각형이고, 땅은 단위 정사각형 1×1로 나누어져 있다. 각 단 www.acmicpc.net 땅 면적의 2차원 누적합을 구하고, 땅의 각 지점을 포인트로 잡고 포인트를 기준으로(포인트를 꼭짓점으로) 나올 수 있는 모든 왼쪽 위, 오른쪽 아래, 오른쪽 위, 왼쪽 아래 면적의 크기와 해당 면적이 나온 개수를 저장하여 포인트를 기준으로 왼쪽 위, 오른쪽 아래 경우에서 같은 면적인 경우의 수와 포인트를 기준으로 오른쪽 위, 왼쪽 아래 면적의 경우에서 같은 면적인 경우의 수를 확인하는 방법으로 문제를..

https://www.acmicpc.net/problem/5446 5446번: 용량 부족 팀포2 덕후 연수는 팀포2를 다운받던 도중 하드 용량이 부족하다는 것을 알았다. 이때는 침착하게 팀포2를 하지 말거나 하드를 새로 사면 되지만 불가능했고, 결국 하드에서 쓸모없는 파일을 지 www.acmicpc.net 트라이를 이용하여 삭제할 문자열과, 남길 문자열을 저장했으며 트라이의 각 노드에서 자식 노드에 대한 삭제할 문자열과 남길 문자열의 정보를 저장하여, 특정 노드에서 와일드카드를 달아서 지울 수 있는지, 또는 해당 노드에서 삭제할 문자열이 끝나서 지워야 하는지를 판단하는 방법으로 문제를 해결했다. 코드 #include #include #include #include using namespace std; i..

https://www.acmicpc.net/problem/12930 12930번: 두 가중치 0번 정점에서 1번 정점으로 가는 최단 경로의 비용을 출력한다. 0번에서 1번으로 갈 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 간선마다 두 개의 가중치가 있으므로, 어떤 정점에서의 지금까지 가중치 1의 합 또는 가중치 2의 합이 지금까지 해당 정점에서 가중치 1의 합 또는 가중치 2의 합보다 작은 경우(앞으로 최솟값을 만들 가능성이 있는 경우)에만 우선순위 큐에 넣는 다익스트라 알고리즘을 이용하여 문제를 해결했다. 코드 #include #include #include #include #include #include using namespace std; int n; vector adj1[25..