![]()
문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 해당 문제는 MST(Minimum Spanning Tree) 알고리즘을 사용하는 문제이다. 왜냐하면 N개의 정점(별)을 이어서 그래프(별)를 만드는데 최소의 비용을 구하라는 문제이기 때문이다. 원래 MST의 문제라면 정점간의 간선에 가중치를 입력으로 제공하지만, 해당 문제는 각 좌표를 제공해서, 정점 간의 거리까지 구하는 문제이다. 가중치를 제공해주지 않았기 때문에 MST를 제대로 ..
![]()
문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 나는 문제를 읽고 DP로 접근을 했는데, 다른 풀이를 보니 DFS로 푼 사람들이 꽤 많았다. 개인적으로 DFS보단 BFS를 선호하고, DFS로 풀 생각을 하지 못했어서 DP로 풀었고, 그에 따른 방법을 설명하겠다. 우선 DP로 선택한 이유는 파이프를 놓는 위치가 이전의 선택들에게 영향을 받는다는 점이었다. 즉 (i, j)로 파이프를 놓을 때, 방향에 따라 ..
![]()
문제 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 문제 풀이 앞선 배열 돌리기 2와 비슷한 문제이다. 거기에선 배열의 원소들을 반시계 방향으로 움직였다면, 이번 문제는 시계방향으로 움직이는 것이다. 그 외에 추가된 것은 연산의 순서를 생각하는 것이다. 회전의 순서에 따라서 배열의 모양이 다르기 때문에 조합이 아닌 순열을 통해서 경우의 수를 산출하고, 회전을 했다. 껍데기의 수는 입력에서 받은 s로 결정하고, r..
