재원블로그 재원블로그

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 트리의 정점 개수는 최대 100만이므로 O(N log N) 이하 알고리즘을 만들어야 한다. 먼저 각 상태를 정의했다.어떤 한 노드를 골랐을 때, 그 노드가 얼리 어답터인 경우에는 주변부의 얼리 어답터 여부는 중요하지 않다.그러나 그 노드가 얼리 어답터가 아닐 경우에는 반드시 주변부 모두가 얼리 어답터야 한다. 이를 점화식으로 정의할 수 있었는데, 다음과 같다.dp[i][0] : 내가 얼리 어답터가 아님 -> sum(dp[next][1])dp[i][1] : 내가 얼리 어답터임 -> sum(min(dp[next][0], dp[next][1])) 이 둘을 정의한 순간 문제는 거의 풀린다. 최악의 경우에도 100만 * 2 배열을 모두 채우면 되므로 1초 안에 충..

이 문제는 세그먼트 트리를 이용해서 풀었다. 시간 제한이 0.7초이므로 약 7,000만번의 연산 안으로 문제를 해결해야 한다. 특정 구간에서의 직사각형 넓이의 최댓값을 구하는 문제로, 세그먼트 트리가 떠올랐다. 처음에는 단순히 세그먼트 트리에 특정 구간의 직사각형 넓이 최댓값을 바로 집어넣었다. 그러나 이런식으로는 풀리지 않는데, 절반씩 구간이 잘리는 형태에서 왼쪽과 오른쪽을 부분적으로 포함하는 범위에서 최댓값이 존재할 수 있기 때문이다. 그래서 세그먼트 트리에는 특정 구간에서의 최소 높이를 가진 인덱스를 저장하고, 이 인덱스로 좌우를 나누는 것이 정답을 맞출 수 있는 포인트이다. #include #include #include #include #include #include using namespace..

이 문제는 세그먼트 트리를 이용하는 문제이다. 이전에 구간 합 구하기 문제의 경우 update 함수를 변경하는 숫자의 차이를 더해서 구했다. 그러나 구간 곱의 경우 한번 0으로 바뀌면 다른 수로 바꿀 수 없는 문제가 발생했다. update 함수를 init과 거의 동일하게 구현함으로써 이 문제를 해결할 수 있었다. #include #include #include #include #include #include using namespace std; #define MAX 1000000 #define MOD 1000000007 typedef long long LL; int N, M, K; int arr[MAX + 1]; LL segment[MAX * 4 + 1]; LL init(int start, int end..

이 문제는 세그먼트 트리를 이용해서 풀었다. 값을 저장하는 쪽에는 모두 long long 을 써줘야 풀린다. 세그먼트 트리를 구현할 수만 있으면 풀리는 기초 문제였다. 몇 가지 주의할 점이 있는데, 첫번째로는 update를 할 때 차이를 더해줘야 하므로 c - arr[b]를 한 값을 update의 인자로 던져줘야 한다. 이 때문에 update 전에 입력 배열인 arr[b] = c를 해줘야 한다. 이거 안해줘서 계속 틀렸었다. 두번째는 update의 dif 또한 long long으로 선언해야한다는 것이다. 값이 int 자료형을 가뿐히 뛰어넘을 수 있기 때문이다. 로직은 단순하나 자료형으로 정답률을 낮춘 문제였다. #include #include #include #include #include using n..

이 문제는 최소 스패닝 트리 문제이다. 별의 개수 n개의 최대는 100이므로, O(N^2) 으로 모든 간선을 만들 수 있다. 모든 별들을 잇는 대신에, 직/간접적으로 이어저야한다. 이는 최소 스패닝 트리를 의미하므로, 크루스칼 알고리즘을 사용해서 문제를 풀었다. 절대/상대 오차를 10^(-2) 까지 허락하므로 cout > n; for (int i = 0; i > x >> y; stars.push_back({ x, y }); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { pair &s1 = stars[i]; pair &s2 = stars[j]; double x = s1.first -..

이 문제는 투 포인터를 이용해서 풀었다. 자연수 N이 최대 400만이므로, 400만 이하의 소수를 찾으면 된다. 연속된 소수의 합으로만 나타내야하므로, 투 포인터를 쓰면 딱 맞다. 만약 acc가 N보다 작다면 right을 증가시켜주고, 크다면 left를 증가시켜 문제를 해결할 수 있다. 400만 이하의 소수의 개수는 약 30만개이므로, 충분히 시간 안에 풀 수 있다. #include #include using namespace std; #define MAX 4000000 int N; bool isPrime[MAX + 1]; vector primes; void init() { for (int i = 0; i

이 문제는 다이나믹 프로그래밍으로 풀었다. 시간 제한이 0.5초로 약 5,000만번의 연산만을 사용해야 한다. dp[i][j] = i번 집을 j 색으로 칠했을 때의 최소 비용 으로 설정하고 문제를 풀었다. 가장 까다로운 부분은 N번 집의 색이 N - 1번, 1번 집과 색이 같지 않아야 한다는 것인데, 이는 dpRed, dpBlue, dpGreen과 같이 첫 집을 어떤 색으로 칠했냐로 설정할 수 있었다. 사실 이럴 필요 없이 배열 하나로 충분하지만, 코드 쓰다 헷갈리지 않기 위해 이렇게 썼다. #include #include #include using namespace std; #define MAX 1000 #define RED 0 #define GREEN 1 #define BLUE 2 int N; int..

이 문제는 이분 탐색을 이용한 LIS 알고리즘으로 풀었다. 전형적인 LIS 문제지만, 최대 배열의 크기가 100만이므로 이분 탐색을 사용해야 한다. 또한 단순히 길이를 출력하는 데서 그치지 않고, 직접 답을 내야하므로 record 배열을 따로 두었다. #include #include #include using namespace std; int arr[1000000]; int N; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 0; i > arr[i]; } vector lis; vector record; for (int i = 0; i < N; i++) { in..