📝 문제 정보 # 링크: https://www.acmicpc.net/problem/12008 🧐 관찰 및 접근 # 흠, 결국 마지막에 사용한 모든 숫자들은 하나의 범위로 나타날 것 같다. 범위를 쪼개는 맛의 DP를 할 수 있나? $\text{DP}[i][j]$: $i$~$j$까지의 숫자를 모두 사용해서 만들어진 수 라고 하면 $O(N^2)$의 시간이 걸린다… 이런 느낌으로 $\log$로 바운드 시킬 수 있q을까? $(1, 1, 1, 2)$ 에서 1들을 2로 묶을 수 있는 경우를 각 인덱스에 대해서 표시 $(2, 1, 2), (1, 2, 2)$ 등으로 나타내져을때, 2들을 4로 묶을 수 있는 경우에 대해 표시.. 그러니까, $(1, 1, 1, 2)$는 2로 묶었을때 다음 인덱스는 $(1, 2, -1, 3)$ 처럼 (0-based) 그러면 뒤로 계속 폴짝폴짝 뛰어다니면서 계산하면, 만들 수 있는 최대값인 58에 대해 $O(N)$번 하면 될거같기도..? 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; vector<vector<int>> v(60, vector<int>(N+1, -1)); rep(i, 0, N) v[A[i]][i] = i; int ans = 0; rep(b, 0, 60){ rep(i, 0, N) if(v[b][i] != -1 && v[b][v[b][i]+1] != -1) v[b+1][i] = v[b][v[b][i]+1]; rep(i, 0, N) if(v[b][i] != -1) ans = max(ans, b); } cout << ans; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10108 번역 문제 # 당신은 간식을 좋아하는 애완용 여우를 키우고 있습니다. 서로 다른 위치(데카르트 평면 위의 점으로 표현됨)에 N명의 이웃이 있으며, 각 이웃은 당신의 애완 여우에게 간식을 나눠줍니다. 각 이웃은 무제한으로 간식을 줄 수 있습니다. 원점(여우가 시작하는 위치)은 이 N개의 위치 중 하나가 아닙니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31740 🧐 관찰 및 접근 # 문제에서 주어진 그래프는 트리로 보인다. 트리에서는 모든 간선이 단절선이므로 하나만 잘라도 두 컴포넌트로 나뉘는것이 자명하다. 간선을 하나 자르고 나면 서브트리 하나와 나머지 부분으로 나뉜다. 서브트리의 가중치는 트리DP를 활용해 미리 계산해둘 수 있고, 나머지 부분은 전체 가중치 합에서 해당 서브트리의 가중치 합만큼을 빼면 된다. $O(N)$에 계산 가능해보인다. 💻 풀이 # 코드 (C++): int dfs(int c, int p){ par[c] = p; DP[c] = W[c]; for(auto nxt : links[c]){ if(nxt == p) continue; DP[c] += dfs(nxt, c); } return DP[c]; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } rep(i, 1, N+1) cin >> W[i]; int SUM = dfs(1, -1); int ans = 2e9; pii ans2 = {-1, -1}; rep(i, 2, N+1) if(ans > abs(DP[i] - (SUM - DP[i]))){ ans = abs(DP[i] - (SUM - DP[i])); ans2 = {i, par[i]}; } cout << ans << '\n'; cout << ans2.first << ' ' << ans2.second << '\n'; } 🔒 구현 코드 잠금
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27421 번역 문제 # Taro는 장난감 철도 선로 세트를 가지고 놀고 있습니다. 모든 선로는 직각 중심각(90도 각도)을 가진 호 모양이지만, 반지름은 다양합니다. Taro는 이 모든 선로를 사용하여 하나의 루프를 만들려고 합니다. 여기서 선로 세트가 하나의 루프를 형성한다는 것은 모든 선로의 양 끝이 다른 선로와 부드럽게 연결되고, 모든 선로가 직접 또는 간접적으로 다른 모든 선로와 연결되어 있을 때를 의미합니다. Taro가 이것을 달성할 수 있는지 여부를 알려주세요.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26969 번역 문제 번역 # Bessie는 “소 유전체학: 다큐멘터리"를 보고 싶지만, 혼자 가고 싶지 않습니다. 불행히도, 그녀의 친구들은 함께 갈 만큼 열정적이지 않습니다! 따라서 Bessie는 친구들이 영화관에 함께 가도록 뇌물을 줘야 합니다. 그녀는 두 가지 뇌물 수단을 가지고 있습니다: 무니(mooney)와 아이스크림 콘입니다.
📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26857 번역 문제 번역 # 두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.