Knapsack

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/27421 번역 문제 # Taro는 장난감 철도 선로 세트를 가지고 놀고 있습니다. 모든 선로는 직각 중심각(90도 각도)을 가진 호 모양이지만, 반지름은 다양합니다. Taro는 이 모든 선로를 사용하여 하나의 루프를 만들려고 합니다. 여기서 선로 세트가 하나의 루프를 형성한다는 것은 모든 선로의 양 끝이 다른 선로와 부드럽게 연결되고, 모든 선로가 직접 또는 간접적으로 다른 모든 선로와 연결되어 있을 때를 의미합니다. Taro가 이것을 달성할 수 있는지 여부를 알려주세요.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18214 번역 문제 번역 # Susan은 식탁 정리는 잘하지만, 사무실 책상 정리는 잘 못합니다. Susan은 방금 일련의 문서들에 대한 서류 작업을 마쳤고, 문서들은 여전히 책상에 쌓여 있습니다. 문서들은 일련번호가 있으며, 상사가 가져왔을 때는 순서대로 쌓여 있었습니다. 그러나 지금은 순서가 완벽하지 않은데, Susan이 너무 게을러서 더미에서 빠져나온 문서들을 제자리에 다시 넣지 않았기 때문입니다. 작업이 끝났다는 소식을 듣고, 상사는 그녀에게 보내고 있는 문서 상자에 문서들을 즉시 반납하기를 원합니다. 물론 문서들은 일련번호 순서대로 상자에 보관되어야 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/26857 번역 문제 번역 # 두 형제 Aldo와 Bondan은 COVID-19 팬데믹 상황이 악화되어 도시가 다시 봉쇄되면서 집에 갇혀 있습니다. 그들은 학기를 마치고 방학 중이지만, 집 밖으로 나갈 수 없다면 무슨 방학을 즐길 수 있을까요? 하지만 지루함은 창의성을 불러일으킵니다. 그들은 지루한 방학 동안 새로운 게임을 만들었습니다.

📝 문제 정보 # 링크: 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/23569 번역 문제 번역 # 문제 설명 # 사람들 간의 상호작용이 주어질 때, 정점이 사람들이고 두 사람이 서로 친구인 경우에만 그들 사이에 간선이 있는 그래프를 정의할 수 있습니다. 이러한 그래프를 소셜 네트워크라고 하며, 예를 들어 대학의 학생들이나 작은 마을의 주민들과 같은 모든 사람들의 집합에 대해 잘 정의됩니다. 최근 몇 년간 소셜 네트워크를 분석하는 완전한 과학 분야가 생겨났는데, 이는 사람들과 그들의 행동에 대한 많은 흥미로운 측면들이 이 친구 관계 그래프의 속성으로 가장 잘 이해되기 때문입니다.