Platinum18 BOJ 2787 : 흔한 수열 문제 문제 링크 : https://www.acmicpc.net/problem/2787 1 x y v - x번째 수부터, y번째 수 중 제일 큰 값은 v 2 x y v - x번째 수부터, y번째 수 중 제일 작은 값은 v 이런 식으로 수열에 관한 정보를 주면 이들을 만족하는 수열을 찾아서 출력하면 된다. 수열의 정보에 관한 문제가 대부분 펜윅트리로 풀려서 그쪽으로 생각을 해봤는데 잘 안 됐다. 그러다가 N 제한이 200 인 것이 이상해서 생각해봤는데 이분매칭이 떠올랐다. 2 ~ 10 번째 수의 최댓값이 15 라면, 2 ~ 10 번째의 각 칸들을 1 ~ 15 와 연결해주고 매칭하면 된다. 하지만, 이 방법은 문제가 있다. 매칭은 정상적으로 되지만, 2 ~ 10 번째 수의 최댓값이 15 면 15가 무조건 존재한다는.. 2022. 8. 14. BOJ 7765 : Supersquare 문제 링크 : http://acmicpc.net/problem/7765 500이하의 자연수 N을 입력받으면, 2N 자리 제곱수를 출력하면 된다. 단, 앞 N자리와 뒤 N자리 또한 제곱수여야 한다. 지금 내가 서술하는 풀이가 정해라면 그리 좋은 문제 같진 않다... Naive 하게 코드를 돌려보면서 규칙을 찾아봤는데 꽤 오래걸렸다. 규칙 찾고 정리하는데 3일 정도 걸렸다. 3일 내내 잡고 있었던 건 아니지만 꽤 어려웠던 건 확실. N이 짝수일 때 (N = 2n + 2 형태) ( 5 * 10(2n+1) - 10(n+1) + 1 )2 를 전개하면 앞 (2n+2) 자리는 (5 * 10n - 1)2 이고 뒤 (2n+2) 자리는 (10(n+1) - 1)2 이다. 이걸 한번에 발견한 것은 아니고 물론 Naive 하게.. 2022. 8. 14. BOJ 24545 : Y 문제 링크 : https://www.acmicpc.net/problem/24545 전형적인 Tree DP 문제이다. 나는 D1, D2, D 세 가지 다이나믹 배열을 정의하여 해결했다. D1[i] := i 번 노드가 꼭대기인 단일 체인의 최대 길이 D2[i] := i 번 노드가 꼭대기인 Y 트리의 최대 크기 ( V 모양도 포함 ) D[i] := i 번 노드가 루트인 서브트리에서의 Y 트리의 최대 크기 이제 DP 식만 잘 세워주면 된다. D1[i] 는 ( 자식들의 D1 들 중 max 값 ) + 1 이다. D2[i] 는 ( 자식들의 D2 들 중 max 값) + 1 과, ( 자식들의 D1 들 중 큰 것 2개의 합 ) + 1 중 큰 값이다. 그럼 D[i]는 어떻게 하면 될까? 1. 서로 다른 두 자식들의 D1 +.. 2022. 8. 14. BOJ 1306 : 달려라 홍준 문제 링크 : https://www.acmicpc.net/problem/1306 언뜻 봐서는 Sliding Window + Segment Tree 또는 Multiset 로 보인다. 구간이 1칸씩 바뀌기 때문에 구간이 바뀔 때마다 Segment Tree 또는 Multiset 으로 O(log N) 쿼리를 하면 총 시간복잡도는 O (N log N) 이다. 하지만 이보다 훨씬 빠른 O(N) 풀이가 있다. deque 를 활용하면 O(N) 만에 매우 간단하게 코드를 짤 수 있다. deque 에 들어갈 것은 기본적으로 (값, index) 순서쌍, 즉 pair 이다. 현재 우리가 처리하는 구간의 인덱스가 [L, R] 이라 해보자. A[L], ..., A[R] 까지의 최댓값을 구하는 것이다. Sliding Window .. 2022. 8. 14. BOJ 1017 : 소수 쌍 문제 링크 : https://www.acmicpc.net/problem/1017 보는 순간 바로 이분매칭이 떠오른다. 하지만 이분매칭은 기본적으로 이분그래프에서 이루어져야 하기 때문에 한 번 막혔었다. 서로 다른 두 수의 합으로 생성된 소수는 무조건 홀수가 될 수 밖에 없다. 또한, 홀수는 무조건 (홀수 + 짝수) 로 만들어질 수 밖에 없다. 따라서, 이 문제는 홀수 / 짝수로 이분그래프를 형성하여 풀면 된다. 다만, 타 문제들과는 달리 첫 수와 매칭될 수 있는 수를 찾아야하기 때문에, 2 ~ N 번째 수와 1번째 수를 수동으로 매칭시킨 후 이분매칭을 실시하면 된다. 2022. 8. 14. BOJ 17167 : A Plus Equals B 문제 링크 : https://www.acmicpc.net/problem/17167 편법으로 파이썬을 쓴 문제... long long 범위의 두 자연수 A, B 가 주어졌을 때 A += A, A += B, B += A, B += B 의 네 연산을 적절히 써서 A == B 가 되게 만들라는 문제다. 이 때, 주의할 점은 꼭 최소 횟수일 필요가 없다는 것이다. A와 B가 같게만 되면 된다. 일반성을 잃지 않고, 마지막에 A 가 커져서 B와 같아졌다고 해보자. 그렇다면, A += A 가 무조건 마지막 연산이 되어야 한다. A += B 를 했는데 B 와 같아질 수 없기 때문. 여기서 조금만 더 나아가면, 마지막은 A += A 가 1번 이상 반복된 형태여야 함을 쉽게 알 수 있다. 즉 A 가 1번 이상 2배가 된다.. 2022. 8. 14. 이전 1 2 3 다음
