BOJ DP
11054 가장 긴 바이토닉 부분 수열
2565 전깃줄
9251 LCS
12865 평범한 배낭
9465 스티커 (DP)
void solve(){
int n; cin>>n;
vector<vector<int>> stickers(2, vector<int>(n));
for(int i = 0; i<2; i++){
for(int j = 0; j<n; j++){
cin>>stickers[i][j];
}
}
vector<vector<int>> dp(2, vector<int>(n, 0));
// dp[i][j] : i번째 row, j번째 col의 sticker를 선택했을 때 최댓값
dp[0][0] = stickers[0][0];
dp[1][0] = stickers[1][0];
if(n >= 2){
dp[0][1] = dp[1][0] + stickers[0][1];
dp[1][1] = dp[0][0] + stickers[1][1];
}
for(int c = 2; c<n; c++){
// c-1의 것을 택할 것인지(그 경우, 대각에 있는 것)
// c-2의 것을 택할 것인지(그 경우, c-1은 택하지 못함)
dp[0][c] = max(dp[1][c-1], dp[1][c-2]) + stickers[0][c];
dp[1][c] = max(dp[0][c-1], dp[0][c-2]) + stickers[1][c];
}
cout<<max(dp[0][n-1], dp[1][n-1])<<'\n';
/*
i, i+1, i+2번째 column에 대해
1) i+1번째와 겹치지 않게 고르기
2) i+1번째와 겹쳐서 dp[i] + max(stickers[0][i+2], stickers[1][i+2])
중 max값
*/
return;
}2294 동전 2
j원을 만들 때, dp[i][j-coins[i]] + 1을 하면 더 작아질 가능성이 있다. ** 틀렸을 경우도 출력해야 한다. 문제 잘 읽기
int main(void) {
cin.tie(0);
cout.tie(0);
std::ios_base::sync_with_stdio(0);
////////////////////// write your code below
int n, k; cin>>n>>k;
vector<int> coins(n);
for(int i = 0; i<n; i++) cin>>coins[i];
sort(coins.begin(), coins.end());
int INF = 99999999;
vector<vector<int>> dp(n, vector<int>(k+1, INF));
// dp[i][j] : i번째까지 coin으로 j원 만들때 드는 최소 동전 개수
for(int i = 0; coins[0] * i <= k; i++){
dp[0][coins[0] * i] = i;
}
for(int i = 0; i<n; i++) dp[i][0] = 0;
for(int i = 1; i<n; i++){
for(int j = 1; j<=k; j++){
dp[i][j] = dp[i-1][j];
if(j >= coins[i])
dp[i][j] = min(dp[i][j], dp[i][j-coins[i]] + 1);
}
}
int answer = dp[n-1][k];
if(answer == INF) answer = -1;
cout<<answer;
//////////////////////
return 0;
}
Codeforces #787 Div. 3
https://codeforces.com/contest/1675
Dashboard - Codeforces Round #787 (Div. 3) - Codeforces
codeforces.com
결과
A, B, C, D번은 시간 내에 풀고 제출했다. 7문제 중 4문제를 맞췄다.
A번
입력에 대한 검증만 하면 되는 간단한 손풀기 문제.
void solve(){
ll a, b, c, x, y;
cin>>a>>b>>c>>x>>y;
string result = "NO";
if(a + c >= x && b + c >= y && a + b + c >= x + y) result = "YES";
cout<<result<<'\n';
}
B번
greedy 문제. 제일 뒤의 것은 줄일 필요가 없으므로, 뒤에서부터 arr[i]와 arr[i-1]을 비교하고, arr[i-1]이 arr[i]보다 크다면 /2를 한다. 만약 arr[i]가 0인 경우에는 어떻게 2로 나누든 풀 수 없으므로, -1이 결과이다.
나는 뒤에서부터 indexing 하기 귀찮아서 처음부터 indexing을 reverse하게 했다.
void solve(){
ll n; cin>>n;
vector<ll> arr(n);
ll input;
for(int i = 0; i<n; i++){
cin>>arr[n-i-1];
}
ll result = 0;
for(int i = 1; i<n; i++){
if(arr[i-1] == 0){
result = -1;
break;
}
while(arr[i-1] <= arr[i]){
arr[i] /= 2;
result++;
}
}
cout<<result<<'\n';
return;
}
C번
규칙 찾기 문제.
잠시만 생각해 보자.
- 제일 앞의 0은 용의자임
- 0 뒤에 오는 0은 참일 수 밖에 없다. '00'과 같이 주어졌을 때, 뒤에 오는 0이 범인인 경우 그 앞사람은 참이기 때문임.
- 같은 논리로, 0 뒤에 오는 ?는 참일 수 밖에 없음. '0?'와 같이 주어졌을 때, ?가 거짓인 경우 그 앞사람은 참이기 때문에, 이미 없는 상태에서 물건을 훔칠 수 없기 때문.
- 그러나 제일 앞의 0은 용의자임.
- 제일 뒤의 1은 용의자임
- 1 앞에 오는 1은 참일 수 밖에 없음. '11'과 같이 주어졌을 때, 앞의 1이 범인일 경우 뒷사람은 참이 되는데 모순이기 때문.
- 같은 논리로, 1 앞에 오는 ?는 참일 수 밖에 없다. '?1'과 같이 주어졌을 때, ?가 거짓인 경우 1은 참인데, 물건이 훔쳐졌지만 존재할 수 없기 때문.
- 그러나 제일 뒤의 1은 용의자임
- 1 앞에 0이 있는 경우
- 01과 같은 경우 - 이런 경우는 주어지지 않음. 뒤의 1이 범인일 경우 앞의 0이 물건을 훔친 것이므로 모순이고, 앞의 0이 범인일 경우 뒤의 1은 참을 말하는데, 있기 때문.
이러한 논리에 의해, 제일 뒤의 1과 제일 앞의 0 사이에 있는 사람들이 용의자가 될 수 있다.
void solve(){
string s; cin>>s;
int zeroidx = s.length(), oneidx = -1;
for(int i = 0; i<s.length(); i++){
if(s[i] == '0'){
zeroidx = i;
break;
}
} // 제일 앞에 있는 zero
for(int i = s.length()-1; i>=0; i--){
if(s[i] == '1'){
oneidx = i;
break;
}
} // 제일 뒤에 있는 one
int answer;
if(zeroidx == s.length() && oneidx == -1) answer = s.length(); // 둘다 찾지 못하면 전부 ?
else if(oneidx == -1) answer = zeroidx + 1; // 1을 못 찾은 경우 - 0 뒤에 있는 것들은 모두 참이니 zeroidx까지
else if(zeroidx == s.length()) answer = s.length() - oneidx; // 0을 못 찾은 경우 - 1 앞에 있는 것은 모두 참이니 oneidx부터 끝까지
else answer = zeroidx - oneidx + 1; // 0, 1 둘 다 있는 경우 - 1과 0 사이(포함)
cout<<answer<<'\n';
}
D번
tree의 중복되지 않는 path 개수를 찾는 문제. 문제를 보자마자 크게 2가지 방식을 생각했는데
- deepest leaf부터 visit 표시 하면서 root로 올라오던가. - 이 방식을 택했다.
- 왜냐하면 문제의 답은 leaf node의 개수이기 때문이며, leaf로부터 unvisited parent까지 탐색한 후 그 path를 reverse하면 되기 때문.
- root부터 dfs를 하고, visit하지 않은 것들부터 다시 dfs를 하는 방법
- 이 경우, tree를 구성하는 데 많은 시간이 걸리리라 생각해서 패스했다.
bool cmp(pii &a, pii &b){
if(a.second == b.second) return a.first > b.first;
return a.second > b.second;
}
// height 찾는 게 잘못되었었음.
int getHeight(vector<int>& parent, int n, vector<pii> &height, int cur_num){
if(height[cur_num].second != -1) return height[cur_num].second;
if(parent[cur_num] == cur_num) return 0;
else return getHeight(parent, n, height, parent[cur_num]) + 1;
}
void solve(){
int n; cin>>n;
vector<int> parent(n+1);
for(int i = 1; i<=n; i++) cin>>parent[i];
vector<pii> height(n+1, {-1, -1}); // .first : number, .second : height
for(int i = 1; i<=n; i++){
height[i] = {i, getHeight(parent, n, height, i)};
}
sort(height.begin(), height.end(), cmp);
// after sort, starts with deepest node
vector<bool> visited(n+1, false);
vector<vector<int>> paths;
// print from deepest node to it's root node
for(int i = 0; i<n; i++){
int cur_num = height[i].first;
vector<int> path;
while(!visited[cur_num]){ // go to unvisited parent node
path.push_back(cur_num);
visited[cur_num] = true;
cur_num = parent[cur_num];
}
if(path.size() != 0) paths.push_back(path);
}
cout<<paths.size()<<'\n';
for(vector<int>& vi : paths){
cout<<vi.size()<<'\n';
for(auto it = vi.rbegin(); it != vi.rend(); it++){
cout<<*it<<' ';
}cout<<'\n';
}
}
Upsolving
D번
구현할 때는 leaf node를 구하는 방법을, depth가 깊은 것부터 정렬해서 그것부터 탐색하는 방식을 택했다. 그래서 여기서 구현 실수가 있었고 오답을 받았다. 근데 이렇게 할 필요 없고, leaf node의 'child가 없다'는 특징을 이용해, 'parent로써 호출된다면 child가 있는 것이므로 leaf가 아니다'를 확인할 수 있고, 이렇게 찾은 leaf node들로부터 역추적을 해 나가면 된다. 또 한 수 배웠다.
vector<bool> leafs(n+1, true);
for(int i = 1; i<=n; i++){
leafs[parent[i]] = false;
}
for(int i = 1; i<=n; i++){
if(leaf[i] == true){
// do search
}
}
E번
구현은 잘 했는데, 세부 디테일에서 좀 깨졌다.
처음 구현한 코드
void solve(){
int n, k; cin>>n>>k;
string s; cin>>s;
map<char, char> m;
for(int i = 0; i<s.length(); i++){
if(m.find(s[i]) != m.end()) continue; // already exist
vector<char> desc_chars;
char final_char = max((int)s[i] - k, (int)'a');
for(char c = s[i]; c > 'a'; c--){
if(m.find(c) == m.end()){ // if not in map then decrease k
k--;
desc_chars.push_back(c);
if(k == 0) break;
} else{
final_char = m[c];
break;
}
}
for(char c : desc_chars){
m[c] = final_char;
}
if(k == 0) break;
}
for(int i = 0; i<s.length(); i++){
if(m.find(s[i]) != m.end()) s[i] = m[s[i]];
}
cout<<s<<'\n';
}그러나 이렇게 풀면 [1 5 4 bcefx]와 같은 경우에서, b를 줄일 때 1번, c를 b로 줄일 때 1번, e를 c로 줄일 때 2번을 쓸 수 있지만 e를 줄이는 과정에서, map에 e가 들어가고, k가 1이 되고, map에 d가 들어가고, k가 0이 되기 때문에, 의도했던 대로 e가 2번 주는 것이 아니라, e를 포함해서 2번 줄여버린다. 해결책은 간단하다.
아래 코드와 같이, k의 감소를 [map에 있을 때까지 줄인 c]가 될 때 까지 c를 계산하고, s[i] - c를 해 버리면 그만큼 줄은 k가 나온다.
void solve(){
int n, k; cin>>n>>k;
string s; cin>>s;
map<char, char> m; m['a'] = 'a';
for(int i = 0; i<s.length(); i++){
if(m.find(s[i]) != m.end()) continue; // already exist
vector<char> desc_chars;
char final_char = max((int)s[i] - k, (int)'a');
char final_c = final_char;
for(char c = s[i]; c >= final_char; c--){
if(m.find(c) == m.end()){
desc_chars.push_back(c);
} else{
final_char = m[c];
final_c = c;
break;
}
}
// k 감소를 아예 별개의 것으로 처리하는 것
k -= (s[i] - final_c);
for(char c : desc_chars){
m[c] = final_char;
}
if(k == 0) break;
}
for(int i = 0; i<s.length(); i++){
if(m.find(s[i]) != m.end()) s[i] = m[s[i]];
}
cout<<s<<'\n';
}
그리고, map으로 짜면 코드가 복잡한 감이 없잖아 있다. 어차피 각 char가 어떻게 감소했는지 정보를 담을 것이면 map으로 할 필요 없고, 크기 26인 배열로 충분하다.
로직은 위의 것과 동일하다. cur_char(s[i])부터 k를 뺐을 때 최소로 올 수 있는 char를 계산하고, cur_char부터 final_char까지 보면서 이미 계산된 c라면 cur_char를 해당 c까지만 당기면 된다. k값도 그만큼 덜 당길 수 있고.
이렇게 final_char를 계산했으면, cur_char부터 final_char까지 isUsed의 값을 변경한다. 이 때, final_char가 unused인 상태라면 isUsed[c]를 final_char로, used인 상태라면 isUsed[final_char]로 두면 된다.
void solve(){
int n, k; cin>>n>>k;
string s; cin>>s;
vector<char> isUsed(26, '0'); // if ith alphabet is unused, isUsed[i] equals '0'
isUsed[0] = 'a';
/*for(int i = 0; i<s.length(); i++){
char cur_char = s[i];
if(isUsed[cur_char - 'a'] != '0') continue; // already exist
char final_char = max((int)s[i] - k, (int)'a'); // 제일 최소로 올 수 있는 char
for(char c = cur_char; c >= final_char; c--){
if(isUsed[c - 'a'] != '0'){ // 만약 이미 계산된 c라면, 해당 c로 final_char를 수정.
final_char = c; // 여기까지만 당기면 됨
break;
}
}
k -= (cur_char - final_char); // k 값 수정
for(char c = cur_char; c >= final_char; c--){ // cur_char부터 final_char까지 값 변경
isUsed[c - 'a'] = (isUsed[final_char - 'a'] == '0' ? final_char : isUsed[final_char - 'a']); // final_char가 unused라면 final_char로, used라면 거기 안에 있는 값으로 set
}
if(k <= 0) break;
}*/ // 해당 코드를 간결하게 줄인 것
for(int i = 0; i<s.length(); i++){
char cur_char = s[i];
if(isUsed[cur_char - 'a'] != '0') continue; // already exist
char final_char = max((int)s[i] - k, (int)'a');
for(char c = cur_char; c >= final_char; c--){
if(isUsed[c - 'a'] != '0'){ // unused then edit end point
final_char = c;
}
else{ // used then
isUsed[c - 'a'] = (isUsed[final_char - 'a'] == '0' ? final_char : isUsed[final_char - 'a']);
}
}
k -= (cur_char - final_char);
if(k <= 0) break;
}
for(int i = 0; i<s.length(); i++){
if(isUsed[s[i] - 'a'] != '0') s[i] = isUsed[s[i] - 'a'];
}
cout<<s<<'\n';
}
F번
보다가 잘 모르겠어서 풀이를 봤다. 풀이는 레전드였다.
문제를 간단히 설명하면 tree인 graph G에서 start vertex x, end vertex y, 중간점 $a_{1}$, ... , $a_{k}$가 있을 때, x - [$a_{1}$, ... , $a_{k}$] - y 순으로 방문하는 것의 최솟값을 얻으라는 것이다. 이 때 []부분은 어떻게 방문하든 상관없다.
이 것의 해답은 graph에 모든 vertex를 방문하는 path인 euler tour를 찾아보면 알 수 있다. 다만, 이 문제에는 방문이 필요없는 vertex가 존재하므로 이렇게 바로 풀 수는 없다... 따라서, 필요없는 vertex를 삭제한다!
삭제 방식은 더 이상 지워지지 않을 때 까지 [a에 없고, x, y가 아닌 leaf node]를 지우는 것이다. 이렇게 반복하면 모든 leaf node는 x, a, y에 속해있을 것이다! 즉, 여기서 더 탐색할 필요가 없다는 것이고, 따라서 x(또는 y)를 시작으로 euler path의 edge 수를 구하면 된다. 그러나 이 문제, 정확한 path를 리턴할 필요가 없고 path 길이를 리턴하는 것이다. 따라서, reduced graph의 edge 개수 * 2가 euler tour의 path 길이이다. 다만, x에서 y로 가는 path는 단 1번만 방문하면 된다. 따라서 답은 ]# of edges in reduced graph * 2]- [# of edges in x to y]이다.
구현에 있어서도 실수가 있었다. leaf node를 지우는 과정에서 leaf node인지 확인을 했어야 했는데 그러지 않아서 모든 edge를 계속 탐색하는 실수를 했다. 그래서 TLE가 났고, 해당 부분을 수정하니 accept되었다.
void solve(){
// input part
string empty;
getline(cin, empty);
int n, k; cin>>n>>k; // n : # of vertex, k : # of things
int x, y; cin>>x>>y; // from x to y
int input;
vector<int> isThing(n+1, false); // isThing[i] == true then ith vertex is job
for(int i = 0; i<k; i++){
cin>>input;
isThing[input] = true; // thing이 있는 house number
}
int from, to;
vector<set<int>> edges(n+1); // adjacent list edges[i] : edge set of ith vertex
for(int i = 0; i<n-1; i++){
cin>>from>>to; // n-1 edges (because of tree)
edges[from].insert(to);
edges[to].insert(from);
}
// delete all leafs not in [a, x, y]
queue<int> leafs;
for(int i = 1; i<=n; i++){
if(isThing[i] == true || i == x || i == y) continue;
if(edges[i].size() == 1){
leafs.push(i);
}
}
while(!leafs.empty()){
int cur_node = leafs.front(); leafs.pop();
if(isThing[cur_node] == true || cur_node == x || cur_node == y) continue;
else{
if(edges[cur_node].size() == 1){ // leaf node has exactly 1 edge.
int to = *edges[cur_node].begin();
edges[cur_node].clear();
edges[to].erase(edges[to].find(cur_node));
leafs.push(to);
}
}
}
// calculate dist from x to y with BFS
vector<bool> visited(n+1, false);
visited[x] = true;
queue<pii> q; q.push({x, 0}); // .first : vertex number ,.second : dist from x
int dist_x_to_y = -1, cur_node, cur_dist;
while(!q.empty()){
cur_node = q.front().first, cur_dist = q.front().second; q.pop();
if(cur_node == y){
dist_x_to_y = cur_dist;
break;
}
for(int next_node : edges[cur_node]){
if(visited[next_node] == false){
visited[next_node] = true;
q.push({next_node, cur_dist + 1});
}
}
}
// get answer
int answer = -1 * dist_x_to_y;
for(int i = 1; i<=n; i++){
answer += (int)edges[i].size();
}
cout<<answer<<'\n';
}
/*
tree로 된 것에서
시작점 x, 도착점 y에 대해
x - a1, ... , ak - y에 대해 움직이는 경우 최소화
x를 root로 잡고 시작
a에 없고, x, y가 아닌 leaf node를 더 이상 삭제되지 않을 때 까지 모두 삭제
-> leaf node는 a에 속해 있거나, y일 것이다. (queue 이용)
reduced graph의 모든 edge는 euler tour로 탐색 가능할 것이다. 다만, x to y의 경로는 1번만 방문되면 된다.
따라서 # of edges in reduced edge * 2 - # of edges in x to y가 답일 것.
*** euler path에 관해 정리할 것
1) leaf를 다 뺀다는 생각
2) 전체 edge에서 x to y를 뺀다는 생각
레전드!
진짜 레전드다 모르면 맞아야지
*/
G번
3차원 DP.. 내일 풀어봐야겠다.
'PS > PS Log' 카테고리의 다른 글
| 22.07.11. 풀었던 문제들 (0) | 2022.07.11 |
|---|---|
| 22.07.10. 풀었던 문제들 (0) | 2022.07.10 |
| 22.07.08. 풀었던 문제들 (0) | 2022.07.08 |
| 22.07.07. 풀었던 문제들 (0) | 2022.07.07 |
| 22.07.06. 풀었던 문제들 (0) | 2022.07.06 |