궤도

문제 풀이 https://myunji.tistory.com/362 [백준] 2470번 : 두 용액 문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용 myunji.tistory.com 이 문제를 응용한 것이다. 두 용액이면 투포인터를 쓰면 될 것인데 3개라 어떻게 할지 고민됐다. 근데 그냥 용액 하나를 고정하고 투포인터를 돌리면 되는 것이었다. 이렇게 초록색을 고정하고 빨간색과 파란색 포인터를 움직이자 N개의 용액이 있을때 초록색 포인터는 0~N-3번 용액까지 움직일 수 있다. 소스코드 #include #include #include #include #inc..

문제 풀이 그냥 모든 배열을 탐색하면서 풀면 시간복잡도가 O(n^2)이 나와서 시간초과가 뜬다. 그러니까 투 포인터를 써야한다. myunji.tistory.com/362 [백준] 2470번 : 두 용액 문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용 myunji.tistory.com 이 문제에서는 양방향에서 좁혀왔는데, 이번엔 한쪽에서 출발할 것이다. 일단 8이하의 모든 소수를 저장한 배열이 있다고 하자. 양 포인터 사이에 있는 모든 수를 합하면 2가 나온다. 우리의 목표 숫자인 8보다 작다. 그럼 오른쪽 포인터를 하나 증가해서 범위를 넓혀준다. 원래 한..

문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용하기 위해 배열을 정렬한다. 투 포인터라는 뜻은 포인터를 2개 사용한단 것이다. 포인터들은 양쪽에서 출발할 때도 있고 한쪽에서 출발할 때도 있는데 이 문제는 양쪽에서 출발할거다. 양 포인터가 가리키는 값들을 합하면 -1이 나온다. 일단 이게 -1과 가장 가까우니까 저 두 조합을 저장해두고... -1은 0보다 작으니까 두 수의 합이 커져야 한다는 뜻이다. 오름차순 정렬이기 때문에 빨간 포인터를 오른쪽으로 옮기면 합이 커지고, 파란 포인터를 왼쪽으로 옮기면 합이 작아질 것이다. 그러니 빨간 포인터를 오른쪽으로 옮..