목록2024/05/07 (2)
체뚱로그
풀이 시간: 3h57m12s90시간 복잡도: O(3^16)공간 복잡도: O(1)문제 입력첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.출력상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.문제 풀이우선 내 초기 문제 풀이는 이러하다. (오류)상어는 현재 방향의 물고기가 있는 모든 칸을 이동할 수 있다는 점에 있어서, dfs 백트래킹을 사용해야겠다고 생각했다.// 물고기 구조체 { 위치(x, y), 방향, 생존 여부 }struct ..
풀이 시간: 46m30s00시간 복잡도: O(N + MlogM + MlogN) // 입력 + 정렬 + 부모노드찾기공간 복잡도: O(N+M)참고 자료: https://medium.com/@lifthus531/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C%EC%99%80-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-63053849b989문제입력입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 줄에 u v d가 주어지며 u학교와..