DP

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/31265 🧐 관찰 및 접근 # 이해가 조금 어려운데, 결국 $N$개의 훈련 상황에서 $d$개의 훈련 가운데 하나를 계속 고르고, 훈련 시간의 합을 최대화 하고싶다. 배낭 문제와 비슷해보인다. $d$개의 선택지가 $N$번 주어지고, 훈련시간 = 무게의 합을 최대화 해야한다. 어? 나이브하게 하면 터지나? 각 단계마다 해야하는 연산량은 $M * d_i$이다. 총 연산량은 $\sum\limits_{i = 1}^N M * d_i \leq 1000 M$ 이니 괜찮을 것 같다. 아니!!!!!!!! 왜틀렸나 했네 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣으려고 한다. 한 훈련을 여러번 쓰지 않게 $M$에 대해 역순으로 돌면서, 잘 처리하자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; rep(i, 0, N){ cin >> D[i]; tv[i].resize(D[i]); } rep(i, 0, N) rep(j, 0, D[i]) cin >> tv[i][j]; knapsack[0][0] = true; rep(i, 1, N+1) for(auto t: tv[i-1]) rrep(j, 0, M+1) if(j - t >= 0 && (knapsack[i-1][j-t] || knapsack[i][j-t])) knapsack[i][j] = true; rrep(j, 0, M+1) if(knapsack[N][j]){ cout << j; return; } cout << -1; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30788 🧐 관찰 및 접근 # 대칭이동을 어떻게 수학적으로 표현할 수 있을까?? 쉬운거부터 해보자. 원래 점이 $(x, y)$에 있었다면 $90\degree$ 직선에 대칭시키면 $(-x, y)$ $45\degree$ 직선에 대칭시키면 $(y, x)$ $60\degree$ 직선에 대칭시키면 $y = \sqrt{3}x$에 대칭인거니까… 아니 이거 너무 까다로운데? 행렬연산은 하기 싫은데.. 각도를 기준으로 생각해보는것도 좋겠다. 극좌표계처럼, 원래 점이 $0\degree$에 있었다면 $60\degree$에 대해 대칭시키면 $120\degree$에 $120\degree$에 대해 대칭시키면 $240\degree$에 이런 느낌인 것 같다. 그렇다면 예제 1번은 $0\degree \rightarrow 120\degree \rightarrow 330 \degree \rightarrow 60 \degree \rightarrow 0$ 인거 같다! $45\degree = 225\degree$라고 생각하고, 가까운 곳을 찾아서 두배로 넘기고, 360으로 모듈러를 취하자. 자, 이제 한번씩 써서 0도로 돌아오는걸 어떻게 만들지? $15\degree$로 만들 수 있는건 $30\degree$ $x\degree$를 $a$에 대칭이동시키면 $(2a - x) \degree$가 되는 것 같다! 이걸 또 $b$에 대칭이동시키면 $(2b - (2a - x))\degree$ 인거같고.. 그러면 플마로 바뀌어가면서 더해지니까 결국 모듈러 360에 대해 두 그룹으로 나눈 합을 일정하게 맞출 수 있는지에 대한 문제로 바뀐다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; if(N%2){ cout << "NO"; return; } int sum = 0; for(auto x: A) sum += x; sum %= 360; DP[0][0][0] = true; rep(i, 0, N) rrep(j, 0, N) rep(k, 0, 360) if(DP[i][j][k]){ int nxt = (k + A[i]*2) % 360; DP[i+1][j+1][nxt] = true; DP[i+1][j][k] = true; } if(DP[N][N/2][sum] || DP[N][N/2][(sum + 180) % 360]){ cout << "YES\n"; vector<bool> used(N); int ci = N, cj = N/2, cs = sum; if(!DP[N][N/2][sum]) cs = (sum + 180) % 360; while(cj){ int prv = (cs - A[ci-1]*2) % 360; if(prv < 0) prv += 360; if(DP[ci-1][cj - 1][prv]){ used[ci-1] = true; ci--; cj--; cs = prv; } else ci--; } vector<int> v1, v2; rep(i, 0, N){ if(used[i]) v1.push_back(i+1); else v2.push_back(i+1); } rep(i, 0, N/2){ cout << v1[i] << ' ' << v2[i] << ' '; } } else cout << "NO"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30208 🧐 관찰 및 접근 # 업무들의 순서때문에, 자유롭게 선택하지 못하는 경우들이 생긴다. 이게 어떤 느낌이지? ![[Drawing 2026-02-07 15.51.45.excalidraw.png]] 예제 입력 1의 순서는 다음과 같다. $1 \rightarrow 2 \rightarrow 3$을 보자. $1$까지 수행해서 중요도 $w_1$, 처리시간 $t_1$을 얻을 수 있다. $2$까지 수행해서 중요도 $w_1 + w_2$, 처리시간 $t_1 + t_2$를 얻을 수 있다. $3$까지 수행해서 $\cdots$ 저렇게 물건을 만들고 나면, 세개중에서 택1을 하는것 빼고는 배낭문제와 동일해진다. 트리 dfs로 냅색을 잘 돌면서 DP를 할 수 있을 것 같다. 근데 안에서 분기가 일어나면… 0이 아닌 모든 $p_i$들은 모두 다르다 라는 문장이 입력에 있다. 💻 풀이 # 코드 (C++): void dfs(int cur, int root, int w, int t){ w += W[cur]; t += T[cur]; bags[root].push_back({w, t}); for(auto nxt: links[cur]) dfs(nxt, root, w, t); } void solve(){ cin >> N >> S; rep(i, 1, N+1) cin >> W[i]; rep(i, 1, N+1) cin >> T[i]; rep(i, 1, N+1){ int p; cin >> p; links[p].push_back(i); } for(auto nxt: links[0]) dfs(nxt, nxt, 0, 0); rep(i, 0, N+2) rep(j, 0, S+1) KS[i][j] = 1e9; KS[0][0] = 0; rep(i, 0, N+1) rep(j, 0, S+1) { KS[i+1][j] = min(KS[i+1][j], KS[i][j]); for(auto [w, t]: bags[i]){ int nxt = min(S, j + w); // } KS[i+1][nxt] = min(KS[i+1][nxt], KS[i][j] + t); } } if(KS[N+1][S] == 1e9) cout << -1; else cout << KS[N+1][S]; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4013 🧐 관찰 및 접근 # 그래프가 DAG라면 위상정렬을 하면서 DP를 진행할 수 있을텐데.. 같은 정점을 여러번 들릴 수 있으므로, 어떤 정점이 사이클 안에 들어있다면 해당 사이클 내의 ATM을 모두 들릴 수 있다! 서로 자유롭게 이동 가능한 관계라면 모두 자유롭게 들릴 수 있으므로, 이를 SCC로 묶어 DAG로 만들자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; DirectedGraph graph(N+1); rep(i, 0, M){ int u, v; cin >> u >> v; graph.add_edge(u, v); } DirectedGraph dag = graph.getCompressedGraph(); int sz = dag.V; vector<int> val(sz), DP(sz, -1e9), indeg(sz, 0); rep(i, 1, N+1){ int X; cin >> X; val[graph.sccId[i]] += X; } int S, P; cin >> S >> P; S = graph.sccId[S]; DP[S] = val[S]; rep(u, 0, sz) for(auto &v: dag.links[u]) indeg[v]++; queue<int> Q; rep(i, 0, sz) if(indeg[i] == 0) Q.push(i); while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto nxt: dag.links[cur]){ DP[nxt] = max(DP[nxt], DP[cur] + val[nxt]); indeg[nxt]--; if(indeg[nxt] == 0) Q.push(nxt); } } int ans = 0; rep(i, 0, P){ int X; cin >> X; X = graph.sccId[X]; ans = max(ans, DP[X]); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: 번역 문제 # Farmer John은 소들의 방목 패턴을 더 잘 관리하기 위해 농장 전체에 일방통행 소 길들을 설치했습니다. 농장은 N개의 목초지로 구성되어 있으며, 편의상 1부터 N까지 번호가 매겨져 있고, 각 일방통행 소 길은 한 쌍의 목초지를 연결합니다. 예를 들어, 목초지 X에서 목초지 Y로 연결되는 길이 있다면, 소들은 X에서 Y로는 이동할 수 있지만 Y에서 X로는 이동할 수 없습니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32607 번역 흐로닝언 박물관 방문 문제 # 흐로닝언 박물관에서는 매일이 다릅니다. 어떤 날은 좋고 평화롭고 조용해서, 하루 종일 아름다운 그림, 조각, 그리고 다른 예술 작품들을 감상할 수 있습니다. 다른 날들은 더 바쁜데, 주말이나 공휴일에는 서두르는 방문객들, 높아진 입장료, 그리고 소리지르는 아이들로 박물관이 가득 찹니다. 이러한 불편함은 매우 다양합니다: 어떤 바쁜 날은 추가 학생 할인(studentenkorting) 덕분에 더 나을 수 있고, 어떤 조용한 날은 지진 위험 때문에 더 나빠질 수 있습니다.