https://www.acmicpc.net/problem/1516 위상 정렬(Topological Sort)은 DAG(Directed Acyclic Graph), 즉 사이클이 없는 유향 그래프에서 Indegree가 0인 정점들을 하나씩 제거해 가면서 정렬하는 알고리즘이다. 위상 정렬을 이용하여 선후 관계를 고려하면서 각 건물이 완성되기까지 걸리는 최소 시간을 구할 수 있다. 스타크래프트를 예로 들자면 스타포트를 올리기 까지의 최소 테크트리는 배럭->팩토리->스타포트이고 템플러 아카이브를 올리고 싶다면 게이트웨이->사이버 네틱스 코어->시타델 오브 아둔->템플러 아카이브 순으로 지어야 한다. 이 때 한 정점 이전에 연결되어 있는 정점들이 여러개 있다면 그 중 가장 시간이 오래 걸리는 것이 최종적으로 다음 ..
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf Core의 개수가 최대 12개 이므로 각각의 Core에 대해서 4가지 방향의 모든 경우의 수를 만들면 된다. 최대 4^12=16777216 이므로 시간 초과에 대해서는 걱정할 필요가 없음을 알 수 있다. 각 경우에 대해서 가장자리에 있는 코어는 어차피 전원에 연결되 있으므로 따로 카운트 해주고 나머지 코어들에 대해서 정해진 방향으로 전선을 만들어 보면서 기존의 코어나 전선과 겹치는 것이 없는지 확인한다. 그리고 정답을 갱신해 갈 때 Core의 개수, 전선 길이의 합 순으로 우선순위를 두어서 한다. 또한 테스트케이스가 여러 개이므로 ..
https://www.acmicpc.net/problem/9657 이기는 위치의 값을 1, 지는 위치의 값을 0이라고 하면 다음 턴을 하나라도 지는 위치로 만들 수 있다면 현재 위치가 이기는 위치이고 다음 턴의 모든 경우가 이기는 위치라면 현재 위치가 지는 위치가 된다. 12345678910111213141516#include int n,d[1001]; int main(){ scanf("%d",&n); for(int i=1;i=0 && !d[i-1]) d[i]=1; if(i-3>=0 && !d[i-3]) d[i]=1; if(i-4>=0 && !d[i-4]) d[i]=1; } printf("%s",d[n]?"SK":"CY"); return 0;}cs