분류 전체보기67 [백준/C++] #1074 Z (divide and conquer) 문제https://www.acmicpc.net/problem/1074 이전에 풀었던 문제인데, 분할정복 문제를 안푼지 하도 오래돼서 나름 분할정복의 클래식 문제라고 생각하는 'Z' 문제를 다시 풀었다. 2달 전에 왜 파이썬으로 풀었었는지는 모르겠지만..ㅋㅋ C++로 다시금 풀어보니까 감회도 새롭고 좋았다. 구상분할정복 유형이라는 걸 알아서 그랬는지 정말 쉽고 빨리 풀었다. 거의 로직 구상 3분에 구현 2분? 정도 걸렸던 것 같다. 나는 보통 입력값을 보고 로직을 구상하는 편인데, Z모양이 반복되는 횟수(?) N과 행과 열이 주어지니까 N의 크기만큼 반복해서 행과 열을 변화시켜가며 방문 순서를 업데이트하면 되겠다!는 생각을 했다. 우선 가장 큰 틀부터 가장 작은 틀까지 차례로 고려하며 행과 열을 통해 각각.. 2024. 8. 24. [백준/C++] #14938 서강그라운드 (Dijkstra) 문제https://www.acmicpc.net/problem/14938구상수색 범위 때문에 낙하지점마다 갈 수 있는 지역들이 다르고, 각 지역들에서 얻을 수 있는 아이템 수가 다르다. 이때, 어떤 지점에 낙하를 해서, 얼마나의 아이템을 얻을 수 있는지 묻는 문제였다. 즉, 한 지점에서 출발을 하면, 최단거리가 수색 범위 이하인 곳들을 추출하고, 그렇게 갈 수 있는 지역들에서 얻을 수 있는 아이템들을 다 더하면 하나의 출발지에서 얻을 수 있는 아이템 수들을 구할 수 있다. 그래서 결국 이문제의 키 포인트는 최단거리가 수색 범위 이하인 곳들을 추출하는 것이고, 각 길마다 거리가 다르므로, 결국 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 데에 사용되는 Dijkstra 알.. 2024. 8. 21. [백준/C++] #1005 ACM Craft (DP) 문제https://www.acmicpc.net/problem/1005구상문제를 보다가 문득 그래프는 없겠지..?라는 생각이 들었다. 만약 그래프에 사이클이 존재한다면, 사이클을 이루는 건물들 간에는 순환 의존 관계가 형성된다. 즉, 건물 A를 짓기 위해 건물 B가 필요하고, 건물 B를 짓기 위해 건물 C가 필요하며, 건물 C를 짓기 위해 다시 건물 A가 필요하게 되는 모순이 발생한다. 이러한 상황에서는 어떤 건물도 완성될 수 없으므로 건물 건설이 불가능하다. 문제에서 모든 건물이 완성될 수 있다고 나와있었기에 그래프에 사이클이 포함되지 않는다는 것을 확증할 수 있었다.!! 구한 이전 건물의 건설 소요시간을 구했다면 다음 건물의 소요시간을 구하는 로직만 짜면 되기에 dp 알고리즘을 사용하는 문제라는 생각이.. 2024. 8. 9. [백준/C++] #1913 달팽이 (Simulation) 문제https://www.acmicpc.net/problem/1913 구상나는 보통 문제에 명시되어있는 조건들을 이용해서 풀이를 찾는 편이다. 입력 조건이 홀수인 자연수 N이라고 나와있었고, 도출해야 하는 최종 배열의 (0,0) 값이 항상 홀수인 자연수의 제곱이 되는 수였다. 그래서 아래 사진과 같이 한겹 한겹 따로 계산해주는 방식을 택했다. 그리고, 상단, 우측, 하단, 좌측 순서로 몇개씩 배열에 넣으면 될까 그림을 그려봤는데, 2 -> 4 -> 6 -> .. 이런식으로 규칙이 명확해서 더 쉽고 빠르게 풀어낼 수 있었다. 시뮬레이션에서는 다시금 첫값, 끝값이 중요하다는 것을 깨달았다. 풀이 + 코드#include#include#include#include#include#define MAX 101.. 2024. 8. 5. 이전 1 2 3 4 5 6 7 8 ··· 17 다음
