Ad_hoc

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34609 번역 문제 # $1$번부터 $n$번까지 번호가 매겨진 $n$송이의 꽃이 왼쪽에서 오른쪽으로 일렬로 놓여 있다. 각 꽃은 백합(lily) 또는 장미(rose) 중 하나이다. $0$ 이상 $n$ 이하의 정수 $j$에 대해, $l_j$를 왼쪽 $j$개의 꽃 중 백합의 수, $r_j$를 오른쪽 $n - j$개의 꽃 중 장미의 수라 하자.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/28359 🧐 관찰 및 접근 # 일단 모두 $P$에 몰아넣거나, $Q$에 몰아넣거나는 가능하니 일단 기본적으로 모든 원소의 합정도는 여유롭게 가능하다. 그런데, 모든 수가 같다고 생각해보자. 그러면 모든 수는 $P$와 $Q$에 동시에 속하는데… 동시에 속할 수 있는 수를 어떻게 제어할 수 있지? 동시에 속한 수가 서로 다른 여러개의 수일 수는 없다. 어떤 수와 그 개수를 곱한 값이 최대인 수를 골라서, 맨 뒤로 보내자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; map<int, int> mp; int ans = 0; rep(i, 0, N){ int x; cin >> x; mp[x]++; ans += x; } int mxIdx = -1, mxVal = -1; for(auto [k, v]: mp){ if(k*v > mxVal){ mxVal = k*v; mxIdx = k; } } ans += mxVal; vector<int> v1, v2; for(auto [k, v]: mp){ if(k < mxIdx) rep(i, 0, v) v1.push_back(k); else if(k > mxIdx) rep(i, 0, v) v2.push_back(k); } rrep(i, 0, v2.size()) v1.push_back(v2[i]); rep(i, 0, mp[mxIdx]) v1.push_back(mxIdx); cout << ans << '\n'; for(auto x: v1) cout << x << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2437 🧐 관찰 및 접근 # $1, 2, 4, 8, 16, \cdots$의 추로 모든 양의 정수를 측정할 수 있음이 자명하다. 이 이유를 살펴보면, $X$라는 무게의 추가 있을때, $X-1$까지의 모든 정수를 표현할 수 없다면 표현할 수 있는 최대치 + 1이 답이 된다. 추를 작은것부터 정렬해서, 빠지는 수 없이 무슨 양의 정수까지 최대한 잴 수 있는지 확인하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<ll> v(N); rep(i, 0, N) cin >> v[i]; sort(all(v)); ll sum = 0; rep(i, 0, N){ if(v[i] > sum + 1){ cout << sum + 1 << "\n"; return; } sum += v[i]; } cout << sum + 1 << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14939 🧐 관찰 및 접근 # 맨 윗줄을 어찌저찌 일처리를 끝냈다고 가정하자. 두번째 줄부터, 그 윗줄의 남은 전구를 끄는 방법은 해당 칸 아래의 스위치를 컨트롤 하는 방법이 유일하다. 이를 사용하면 맨 윗줄을 처리할 수 있는 방법 $= 2^{10} = 1024$가지에 대해 해볼 수 있고, 시뮬레이션은 $100 \times 100 = 10000$번으로 충분히 시간 내로 들어온다. 맨 아랫줄에 켜진 전구가 남아있으면 안됨에 유의한다. 💻 풀이 # 코드 (C++): void solve(){ vector<string> board(10); rep(i, 0, 10) cin >> board[i]; int answer = 1e9; rep(bit, 0, 1<<10){ vector<string> cboard = board; int cnt = 0; auto press = [&](int r, int c){ cnt++; cboard[r][c] = (cboard[r][c] == 'O' ? 'X' : 'O'); if(r > 0) cboard[r-1][c] = (cboard[r-1][c] == 'O' ? 'X' : 'O'); if(r < 9) cboard[r+1][c] = (cboard[r+1][c] == 'O' ? 'X' : 'O'); if(c > 0) cboard[r][c-1] = (cboard[r][c-1] == 'O' ? 'X' : 'O'); if(c < 9) cboard[r][c+1] = (cboard[r][c+1] == 'O' ? 'X' : 'O'); }; rep(c, 0, 10) if(bit & (1 << c)) press(0, c); rep(r, 1, 10) rep(c, 0, 10) if(cboard[r-1][c] == 'O') press(r, c); bool ok = true; rep(c, 0, 10) if(cboard[9][c] == 'O') ok = false; if(ok) answer = min(answer, cnt); } if(answer == 1e9) cout << -1 << '\n'; else cout << answer << '\n'; } 🔒 구현 코드 잠금

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

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34830 🧐 관찰 및 접근 # 문제 상황을 차근차근 살펴보자 $a, b$가 있을 때, $a - b$ 를 한번 지나가면 된다. $a, b, c$가 있을 때, $a - b, b- c, c-a$를 한번씩 지나가야한다. $a, b,c ,d$가 있을 때, $a-b, a-c, a-d, b-c, b-d, c-d$를 한번씩 지나가야 한다. 이를 그래프 이론으로 해석할 수 있지 않을까? 그래프가 있고, 각 간선을 한번씩 지나되, 시점과 종점이 달라도 된다 한붓그리기가 가능한가? 이제 이 문제는 오일러 경로를 가능하게 하는 문제로 바뀐다. 오일러 경로는, 홀수점이 두개 이하일때 가능하다. 정점이 $N$개 있다고 하면, 그래프는 완전그래프이므로 각 정점에 붙어있는 간선은 $N-1$개이다. $N$이 홀수라면, 모든 $N$개의 정점은 짝수점이다. $N$이 짝수라면, 모든 $N$개의 정점은 홀수점이다. 따라서, $N-2$개의 점들을 연결해서 홀수점이 2개가 되도록 만드는것이 최적이다. 💻 풀이 # 코드 (C++): void solve(){ ll N; cin >> N; ll ans = N * (N-1) / 2; if(N%2 == 0) ans += N/2 - 1; cout << ans; }