프로그래밍

https://codeforces.com/contest/1547/problem/A

[난이도] Div.3
[유형] 구현

[풀이]
tc가 10^4인걸 생각 못하고 BFS로 풀었다가 TLE를 맞았습니다.
A,B,F가 모두 다른 점이므로 O(1)에 계산이 가능하다는 것을 파악해야합니다.
만약 A,B,F가 일직선상에 있지 않다면 최단거리가 여러 가지이므로 F에 의해 한 경로가 막힌다 하더라도
다른 경로를 이용하면 되므로 무조건 dist(A,B) 만큼이 최단 거리가 됩니다.

만약 A,B,F가 일직선 상에 있고 A,B 사이에 F가 있다면 유일한 최단 거리 dist(A,B)가 막힌 것이므로
F를 피해서 가는 이동 2를 더해줘야 하므로 dist(A,B)+2가 정답이 됩니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int tc,sy,sx,ey,ex,fy,fx;
bool visit[1001][1001];

bool same(int a,int b,int c){
    return (a==b&&b==c);
}
bool between(int a,int b,int c){
    if(a>c) swap(a,c);
    return (a<b&&b<c);
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d%d%d%d",&sx,&sy,&ex,&ey,&fx,&fy);
        int ans = abs(sx-ex)+abs(sy-ey);
        if(same(sx,fx,ex)&&between(sy,fy,ey) || same(sy,fy,ey)&&between(sx,fx,ex)){
            ans+=2;
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round731-Div.3/A.cpp

https://www.acmicpc.net/problem/14719

[난이도] Gold5
[유형] 구현

[풀이]
0~W-1 열이 있을 때 어떤 인덱스 i 열에 고이는 물의 양을 구하려면
1) 1~i-1 블록의 높이중 최댓값, i+1~W-1 블록의 높이중 최댓값을 구하고
둘중 더 작은 값 k를 구한다.
2) i 블록의 높이 h가 k보다 작다면 물이 고일 수 있고 그 양은 k-h 만큼이다.

이런식으로 1~W-2 블록을 순회하면서 각 열에서 고일 수 있는 물을 더해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int H,W,a[500];
int getMax(int l,int r){
    int ret=0;
    for(int i=l;i<=r;i++){
        ret=max(a[i],ret);
    }
    return ret;
}
int main(){
    scanf("%d%d",&H,&W);
    for(int i=0;i<W;i++) scanf("%d",&a[i]);
    int ans=0;
    for(int i=1;i<W-1;i++){
        int k = min(getMax(0,i-1),getMax(i+1,W-1));
        if(a[i]<k) ans+=k-a[i];
    }
    printf("%d",ans);
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/14719.cpp

https://www.acmicpc.net/problem/5430

[난이도] Gold5
[유형] 구현

[풀이]
배열에 직접 원소를 넣어서 reverse,pop 연산을 하게되면 시간초과가 발생한다.
배열 대신 배열의 왼쪽 index 'l', 오른쪽 index 'r', 현재 뒤집혀 있는지를 체크하는 flag 'rvs' 를 유지하면서
R,D 커맨드마다 위 변수들을 적절히 조절해주면 된다.

주의할 점은 배열에 원소가 모두 삭제되었을 때 배열을 뒤집는 R 연산을 해도 error가 아니라는 점이다.

#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int T,N,K;
string cmd,s;
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie();
    cin >> T;
    while(T--){
        cin >> cmd >> N >> s;
        vector<int> v;
        int prev=1;
        for(int i=1;i<s.size();i++){
            if(i-prev>0){
                if(s[i]==',' || s[i]==']'){
                    string t = s.substr(prev,i-prev);
                    v.push_back(stoi(t));
                    prev=i+1;
                }
            }
        }
        int l=0,r=N-1;
        bool rvs=0,err=0;
        for(auto& c : cmd){
            if(c=='R') rvs = !rvs;
            else{
                if(l>r) {
                    err=1;
                    break;
                }
                if(rvs==0) l++;
                else r--;
            }
        }
        if(err){
            cout << "error" << '\n';
            continue;
        }
        cout << '[';
        if(!rvs) {
            for(int i=l;i<=r;i++){
                cout << v[i];
                if(i!=r) cout << ',';
            }
        }else{
            for(int i=r;i>=l;i--){
                cout << v[i];
                if(i!=l) cout << ',';
            }            
        }
        cout << ']' << '\n';   
    }
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/5430.cpp

https://www.acmicpc.net/problem/9093

[난이도] Bronze1
[유형] 구현

[풀이]
reversed 함수를 이용해 뒤집기

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    while(n-->0){
        var sp = readLine().split(" ");
        for(a in sp){
            print(a.reversed()+' ')
        }
        println()
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Bronze1/9093.cpp

https://www.acmicpc.net/problem/9081

[난이도] Gold4
[유형] 구현

[풀이]
next_permutation을 이용해서 두번째로 나오는 숫자를 구하면 된다.

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int tc;
int main(){
    cin >> tc;
    while(tc--){
        string s,ans;
        cin >> s;

        int cnt=0;
        do{
            ans = s;
            if(++cnt==2) break;
        }while(next_permutation(s.begin(),s.end()));
        cout << ans << '\n';
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/9081.cpp

https://codeforces.com/contest/1490/problem/B

[난이도] Div.3
[유형] 구현

[풀이]
크기 3짜리 배열에 나머지가 0,1,2인 숫자들의 개수를 각각 저장 뒤.
index 0,1,2 각각에서 시작해서 N/3만큼만 남기고 순차적으로 우측( a[(i+1)%3] ) 으로
밀어보는 시도를 한다.
최대 2회까지 밀어보고 나머지를 민 타겟의 위치가 N/3이 되게 되면 그때가 최적의 정답이다.

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int tc,n,a[50];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int ans = 0;
        for(int i=1;i<n;i++){
            int p=a[i-1],q=a[i];
            if(p>q) swap(p,q);
            if(2*p>=q) continue;
            int cur=p;
 
            for(int cur=2*p;cur<q;cur*=2){
                ans++;
            }  
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round702-Div.3/B.cpp

https://www.acmicpc.net/problem/20058

[난이도] Gold4
[유형] 구현

[풀이]
문제에서 시키는대로 구현하기

#include <cstdio>
#include <algorithm>
using namespace std;
int N,Q,map[70][70],tmp[70][70],dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
bool visit[70][70];
int dfs(int y,int x){
    visit[y][x]=1;
    int ret=1;
    for(int i=0;i<4;i++){
        int ty=y+dy[i],tx=x+dx[i];
        if(map[ty][tx] && !visit[ty][tx]) ret += dfs(ty,tx);
    }
    return ret;
}
void move(int y,int x,int k){
    for(int l=k;l>=2;l-=2){    
        for(int i=0;i<l;i++) {
            tmp[y+i][x+l-1] = map[y][x+i];
            tmp[y+l-1][x+l-1-i] = map[y+i][x+l-1];
            tmp[y+l-1-i][x] = map[y+l-1][x+l-1-i];
            tmp[y][x+i] = map[y+l-1-i][x];
        }
        y++,x++;
    }
}
void query(int n){
    int k = 1<<n;
    for(int i=1;i<=(1<<N);i+=k)
        for(int j=1;j<=(1<<N);j+=k) move(i,j,k);
}
int main(){
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=(1<<N);i++){
        for(int j=1;j<=(1<<N);j++){
            scanf("%d",&map[i][j]);
            tmp[i][j]=map[i][j];
        }
    }
    int sum=0,sum2=0;
    while(Q--){
        int q;
        scanf("%d",&q);
        if(q!=0){
            query(q);
            for(int i=1;i<=(1<<N);i++){
                for(int j=1;j<=(1<<N);j++){
                    map[i][j]=tmp[i][j];
                }
            }
        }
        sum=0;
        for(int i=1;i<=(1<<N);i++){
            for(int j=1;j<=(1<<N);j++){
                int cnt=0;
                if(map[i][j]==0) continue;
                for(int k=0;k<4;k++){
                    if(tmp[i+dy[k]][j+dx[k]]>0) cnt++;
                }
                if(cnt<3) map[i][j]--;
                sum+=map[i][j];
            }
        }
        for(int i=1;i<=(1<<N);i++)
            for(int j=1;j<=(1<<N);j++)
                tmp[i][j]=map[i][j];
    }
    for(int i=1;i<=(1<<N);i++)
        for(int j=1;j<=(1<<N);j++)
            if(map[i][j] && !visit[i][j]) sum2=max(sum2,dfs(i,j));
    printf("%d\n%d",sum,sum2);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/20058.cpp

https://www.acmicpc.net/problem/8981

[난이도] Gold4
[유형] 구현

[풀이]
코드를 보고 역추적하는 문제이다. 인덱스와 값의 관계를 잘 파악해야 한다.
어떤 Y에 대해서도 X는 무조건 존재하므로 -1인 출력은 신경쓰지 않아도 된다.

#include <cstdio>
int N,a[30],b[30];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);

    int idx=0;
    b[0]=a[0];
    for(int j=1;j<N;j++){
        int mv = b[idx];
        idx=(idx+mv)%N;
        while(b[idx]!=0) idx=(idx+1)%N;
        b[idx]=a[j];
    }
    printf("%d\n",N);
    for(int i=0;i<N;i++) printf("%d ",b[i]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/8981.cpp