https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq 1~12월까지의 수영장 이용 계획이 있고 1일, 1달, 3달, 1년 이용권의 요금이 주어질 때, 모든 이용 계획을 커버하는 최소 비용을 구하는 문제이다. 재귀함수를 적절히 설계해서 모든 경우를 찾아서 그 중 최소값을 구하면 된다. go(now,cost) = 현재 위치가 now이고 지금까지 쓴 비용이 cost ans의 초기값을 1년 이용권으로 두고 1. 1일 이용권 사용시 cost에 해당 월 (now) 이용 날짜 * 1일 이용권 사용비용을 더해주고 위치를 1 더한다.2. 1달 이용권 사용시 cost에 1달 이용권 사용비용을 더해주고 ..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq 다음 3가지 규칙에 따라 등산로를 만들 때 가장 긴 등산로의 길이를 구하는 문제이다. 1. 등산로는 가장 높은 봉우리에서 시작해야 한다.2. 높은 봉우리에서 동서남북으로 점점 낮아져야 한다. 대각선은 연결할 수 없다.3. 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 깎을 수 있다. 우선 가장 높은 봉우리들을 저장하고 DFS 백트래킹으로 각 지점들에서 시작하는 등산로들을 찾아 볼 수 있다. 그렇다면 3번 규칙은 어떻게 고려할 것인가? 경로를 탐색할 때 만약 현재 위치보다 새로운 위치의 높이가 더 낮다면 그냥 가면 된..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr&categoryId=AWBJKA6qr2oDFAWr&categoryType=CODE 유니온 파인드를 구현하자. 123456789101112131415161718192021222324252627#include int p[1000001];int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); }void Union(int x,int y) { p[Find(x)]=Find(y); } int main(){ int t; scanf("%d",&t); for(int k=1;k
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf Core의 개수가 최대 12개 이므로 각각의 Core에 대해서 4가지 방향의 모든 경우의 수를 만들면 된다. 최대 4^12=16777216 이므로 시간 초과에 대해서는 걱정할 필요가 없음을 알 수 있다. 각 경우에 대해서 가장자리에 있는 코어는 어차피 전원에 연결되 있으므로 따로 카운트 해주고 나머지 코어들에 대해서 정해진 방향으로 전선을 만들어 보면서 기존의 코어나 전선과 겹치는 것이 없는지 확인한다. 그리고 정답을 갱신해 갈 때 Core의 개수, 전선 길이의 합 순으로 우선순위를 두어서 한다. 또한 테스트케이스가 여러 개이므로 ..