Stargazer

접근: 용액을 모두 탐색 하긴 해야 하기 때문에, 탐색방법 중에 두포인터를 이용하도록 하겠다. (막상 두포인터인지는 모르겠다...) 전략: 입력 받은 값을 오름차순으로 정렬 후에, 작은 것부터 하나씩 기준을 정한다. 그 기준으로 오른쪽 배열에서 가장 왼쪽과 가장 오른쪽을 먼저 선택하고, 용액을 합쳤을 때 절댓값이 작게 되도록, 그 간격을 좁히는 방향으로 점점 이동한다. 만나면 다음 기준으로 옮기고 반복한다. 코드: #include #include #include #include using namespace std; int n; // 3~5000 long long sum = 3000000001; vector input; int main(){ cin >> n; input.resize(n); for(int i..

접근: 처음에는 어떻게 접근 해야 할지 직접 그려보면서, 관계를 파악해보았다. 대충 봐도 그래프 이론으로 풀어야 하는데, 그 중 순서 정렬이 필요하기 때문에 위상 정렬로 풀어야 한다는 걸 알 수 있다. 전략: 대소 관계를 표현하기 위해 입력을 digraph(유향그래프) 형태로 입력을 받는다.(형식은 자유 - 행렬, 인접리스트) 진입 차수가 0인 노드부터 큐에 넣고, 큐에서 하나씩 제거하면서 출력한다. 제거한 노드가 가리키는 다른 노드의 진입 차수를 한개 줄이고, 만약 0이라면 큐에 삽입한다. 코드: #include #include #include using namespace std; int n,m; vector comp; vector income; int main(){ cin >> n >> m; comp..

접근: 스도쿠 자체로 크기가 9x9로 정해 있기 때문에, 백 트래킹 이 가능한 크기다. 따라서 백트래킹으로 하나씩 전부 조사하되 사전식으로 조사하면 된다. 전략: 앞에서 부터 하나씩 입력 받을 때, 0의 위치와 갯수를 입력받아서 백트래킹으로 각 점을 대입하면서 답을 찾아본다. 코드: #include #include using namespace std; int map[9][9]; int cnt = 0; bool flag = false; vector vac; bool visit[81] ={false,}; void print(){ for(int i=0;i

접근: 어떤 자연수가 주어지면 그것보다는 작은 소수의 합의 갯수를 구하는 것이므로, n보다 작은 소수의 배열을 구하고, 그에 맞는 구간 합을 구하면 된다. 전략: 소수를 구하는 것은 에라스토테네스의 체를 이용하여 구하면 되고, 구간합은 투 포인터(two pointers)를 이용하여 구하면 된다. 코드: #include #include #include using namespace std; vector sosu; //n이하 소수 배열 bool so[4000001]; //소수 판별 배열 int n; int sum = 0; int s = 0, e = 0; int res = 0; int main(){ cin >> n; for(int i=2;i= sosu.size()) break; sum += sosu[e++]; ..

접근: 전광판이 무한으로 연결되어서 나오는 형태의 광고이기 때문에 적어도 L 만큼은 광고 할 수 있음이 보장이 되어있다. 문제는 주어진 문자열에 대해서 어떤 광고를 말하는 것인지 최소 길이를 구하는 것이다. 문제의 예에서도 말했듯이, aabaaa 가 주어졌다면, aaba 는 광고가 가능한 최소 길이이다 중요한 것은 반복할 문자열이 그 뒤에 얼마나 겹치는 가이다. 그래서, 최소 길이를 구하려면, 길이 L 에서 최대한 겹치는 부분을 제외한 나머지 부분으로 구해야한다. 위 예로 들자면 aabaaa 처럼 뒤에 2개가, 길이 L이 주어졌을 때, 반복하면 최대로 겹치는 부분이다. 그렇기 때문에 저 2개를 제외한 나머지 부분이 반복해야 할 최소 길이가 된다. 전략: KMP 알고리즘을 이용하여, 하나씩 길이를 늘려가면..