📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2132 🧐 관찰 및 접근 # 트리에서 특정 경로 위에서 노드들의 가중치의 합 트리의 경로란, 하나의 간선을 두번 지나지 않으며 $a_i \in V, (a_i, a_{i+1}) \in E$ 를 만족하는 집합 다시말해, 그냥 특정 간선을 두번 타지 않고 갈 수 있는 시점~종점의 길 어떻게 구할지 생각해보자 어떤 점 $a_0$에서 경로를 시작한다고 해보자. 그 다음에 갈 수 있는 점은 $a_0$의 자식중 한곳에만 갈 수 있다. 한 자식한테 들어간다면, 다시 나올수가 없기 때문에 그 자식을 $a_1$이라고 한다면, 마찬가지로 그 자식중 한곳에만 갈 수 있다. 어? 이거 DFS아닌가? DFS처럼 할 수 있는 것 같다. 그러면 자식중에 어디로 가야하는가? 물론 가장 열매를 많이 먹을 수 있는 곳으로! 💻 풀이 # 코드 (C++): int N; vector<int> links[10010]; int val[10010]; int dfs(int cur, int par){ int ret = 0; for(auto nxt: links[cur]){ if(nxt == par) continue; ret = max(ret, dfs(nxt, cur)); } return ret + val[cur]; } void solve(){ cin >> N; rep(i, 1, N+1) cin >> val[i]; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } int ans = 0, idx = 1; rep(i, 1, N+1){ int res = dfs(i, -1); if(res > ans){ ans = res; idx = i; } } cout << ans << ' '<< idx << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32607 번역 흐로닝언 박물관 방문 문제 # 흐로닝언 박물관에서는 매일이 다릅니다. 어떤 날은 좋고 평화롭고 조용해서, 하루 종일 아름다운 그림, 조각, 그리고 다른 예술 작품들을 감상할 수 있습니다. 다른 날들은 더 바쁜데, 주말이나 공휴일에는 서두르는 방문객들, 높아진 입장료, 그리고 소리지르는 아이들로 박물관이 가득 찹니다. 이러한 불편함은 매우 다양합니다: 어떤 바쁜 날은 추가 학생 할인(studentenkorting) 덕분에 더 나을 수 있고, 어떤 조용한 날은 지진 위험 때문에 더 나빠질 수 있습니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/12858 🧐 관찰 및 접근 # $\text{gcd}(n, n+1)$은 몇일까? $G = gcd(n, n+1)$이 어떤 소수 $p$를 약수로 가진다고 하자. 이때 $p$는 간격 $p$마다 한개씩 존재한다. $p = 2$면 $p$를 약수로 가진 수는 $2$칸마다 존재한다. 따라서 연속된 두 수는 어떤 공약수인 소수 $p$를 가질 수 없다! 따라서 $\text{gcd}(n, n+1) = 1$임을 알 수 있다. 같은 방법으로, $\text{gcd}(a, b) = \text{gcd}(a, b-a)$ 임도 알 수 있다. 유클리드 호제법에서도 알 수 있듯이! 구간 쿼리지만, Lazy하게 연산하기는 쉽지 않아보인다. 하지만 $\text{gcd}(x_a, x_{a+1}, x_{a+2}, \dots, x_b)$ 를 $\text{gcd}(x_a, x_{a+2} - x_{a+1}, x_{a+3} - x_{a+2}, \dots, x_b - x_{b-1})$ 이라고 생각하면, 바뀌는 수는 생각보다 많지 않다! Lazy한 합 연산과 최대공약수에 대한 그냥 세그먼트 트리로 풀 수 있지 않을까? 사실 Lazy부분도 구간 덧셈, 점 쿼리이므로 그냥 세그로 바꿀 수 있지만, 귀찮으니까 ㅋㅋ 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; LazySegmentTree LST(N); ST.init(N-1); vector<ll> A(N); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) LST.set(i, A[i]); LST.build(); rep(i, 0, N-1) ST.set(i, abs(A[i+1] - A[i])); ST.build(); int Q; cin >> Q; while(Q--){ ll op, a, b; cin >> op >> a >> b; a--; b--; if(op){ LST.update(a, b, op); if(a-1 >= 0) ST.update(a-1, abs(LST.query(a-1, a-1) - LST.query(a, a))); if(a+1 < N) ST.update(a, abs(LST.query(a+1, a+1) - LST.query(a, a))); }else{ cout << gcd(LST.query(a, a), ST.query(a, b-1)) << '\n'; } } } 🔒 구현 코드 잠금