프로그래밍

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

[난이도] Gold5
[유형] 수학

[풀이]
수열의 숫자들간의 관계를 그래프로 표현한 뒤, 모든 수에서 DFS를 돌려보면서
깊이가 N-1까지 도달했을 때, 즉 모든 수를 나누기3, 곱하기2 연산으로 방문을 완료했을 경우의 방문 순서를 출력해주면 됩니다.

예를 들어,
4 8 6 3 12 9
수열이 있을 경우
8을 만들려면 4 또는 24가 있어야 하는데 24는 수열에 없으므로
4->8 간선만 만들어주면 됩니다.
이런식으로 모든 수에 대해 어떤 수로부터 만들 수 있는지를 파악하여 간선을 만들어주면 됩니다.
숫자와 index를 매핑해주기 위해 map을 이용하였습니다.

#include <cstdio>
#include <vector>
#include <string>
#include <map>
using namespace std;
using ll = long long;
int N;
ll B[101];
map<ll,int> m;
vector<int> adj[101];
bool sol(int n,string s,int dep){
    if(dep==N-1){
        printf("%s",s.c_str());
        return true;
    }
    for(auto nxt : adj[n]) if(sol(nxt,s+" "+to_string(B[nxt]),dep+1)) return true;
    return false;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%lld",&B[i]);
        m[B[i]]=i;
    }
    for(int i=0;i<N;i++){
        if(m.find(B[i]*3) != m.end()) adj[m[B[i]*3]].push_back(i);   
        if(B[i]%2==0 && m.find(B[i]/2) != m.end()) adj[m[B[i]/2]].push_back(i);
    }
    for(int i=0;i<N;i++) if(sol(i,to_string(B[i]),0)) return 0;
}

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

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

[난이도] Gold5
[유형] 이분탐색

[풀이]
N<=100000 이므로 N^2개의 모든수의 짝을 구해보기엔 시간이 오래걸리므로
이분탐색을 이용하였습니다.
배열 A를 정렬시킨 뒤,
A[i] (i:0~N-1)를 고정시키고 A[i]~A[N-1] 의 숫자 중 조건을 가장 잘 만족시키는
숫자 A[j]를 찾으면 됩니다.
A[j]-A[i] >= M 이 조건이므로 A[i]~A[N-1]의 숫자 A[j] 중 A[j] >= A[i]+M 을 만족하는
j를 lower_bound를 이용해 찾을 수 있습니다.

아래 코드와 같이 lower_bound(a+i,a+N,a[i]+M) 는 a[i]+M 이상인 최솟값의 iterator를 반환하므로
(반환된 iterator:it)-A 의 값이 곧 index j의 값이 됩니다.
A[j]-A[i]는 정답의 후보가 될 수 있으므로 ans 값을 업데이트 해주면 됩니다.

#include <algorithm>
#include <cstdio>
using namespace std;
using ll = long long;
int N;
ll M,a[100001];
int main(){
    scanf("%d%lld",&N,&M);
    for(int i=0;i<N;i++) scanf("%lld",&a[i]);
    sort(a,a+N);
    int ans = 2e9;
    for(int i=0;i<N;i++){
        int idx = lower_bound(a+i,a+N,a[i]+M)-a;
        if(idx<N) ans = min(int(a[idx]-a[i]),ans);
    }
    printf("%d",ans);
}

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

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

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

[풀이]
결과 문자열 T의 뒤부터 확인하면서, A가 있으면 첫번째 규칙,
B가 있으면 두번째 규칙을 거꾸로 적용해주면서
T가 S가 되는 순간이 있으면 1을 아니면 0을 출력해주면 됩니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string A,B;
int main(){
    cin >> A >> B;

    while(!B.empty()){
        if(A==B) {
            cout << "1";
            return 0;
        }
        if(B.back()=='A') B.pop_back();
        else {
            B.pop_back();
            reverse(B.begin(),B.end());
        }
    }
    cout << "0";
}

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

https://programmers.co.kr/learn/courses/30/lessons/87390

[난이도] level2
[유형] 수학

[풀이]
n이 3일 때, 아래와 같이
1(1,1) 2(1,2) 3(1,3)
2(2,1) 2(2,2) 3(2,3)
3(3,1) 3(3,2) 3(3,3)

row,column 중 최댓값이 행렬의 값이 됩니다.
그러므로 left~right 값을 (row,column)의 좌표로 변환해주기만 하면
쉽게 답을 구할 수 있습니다.
left~right의 임의의 값 i에 대해 (row,column) 은 (row/n+1,row%mod+1) 이 됩니다.

#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;
vector<int> solution(int n, ll left, ll right) {
    vector<int> answer;
    for(ll i=left;i<=right;i++){
        answer.push_back(max(i/n,i%n)+1);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/n^2_배열_자르기.cpp

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

[난이도] Gold4
[유형] 플로이드 와샬

[풀이]
플로이드 와샬을 이용해 각 지점간 거리를 구해놓으면 정답을 쉽게 구할 수 있습니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int T,N,M,K,dist[101][101],inf=9e8,frd[101];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=N;j++) {
                dist[i][j]=inf;
                if(i==j) dist[i][j]=0;
            }
        }
        while(M--){
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            dist[v][u]=dist[u][v]=d;
        }
        scanf("%d",&K);
        for(int i=0;i<K;i++) scanf("%d",&frd[i]);

        for(int k=1;k<=N;k++){
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    dist[i][j] = min(dist[i][k]+dist[k][j],dist[i][j]);
                }
            }
        }
        int ans=inf,idx=-1;
        for(int i=1;i<=N;i++){
            int v=0;
            for(int j=0;j<K;j++) v+=dist[i][frd[j]];
            if(ans>v){
                idx=i;
                ans=v;
            }
        }
        printf("%d\n",idx);
    }
}

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

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

[난이도] Gold4
[유형] DP

[풀이]
DP를 이용해 O(N*M)에 해결이 가능합니다.
dp[i][j] : (i,j) 가 오른쪽 아래 모서이리 때 만들 수 있는 정사각형의 변의 최대 길이.
점화식을 위와 같이 정의했을 때, dp[i][j]가 최소 1이 되려면 map[i][j]==0 이어야 합니다.
이제 미리 구해져 있는 dp[i-1][j-1],dp[i][j-1],dp[i-1][j] 값들을 이용해 최대 길이를 구할 수 있습니다.
위 세 개의 값을 1개라도 0이면 1보다 큰 정사각형을 만들 수 없기 때문에 예외처리 해줍니다.

그 후엔 아래와 같은 점화식으로 세 값중 가장 작은 값에 1을 더한 값이 dp[i][j]가 됩니다.
dp[i][j]=min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;

그림을 그려보시면 쉽게 파악이 되실 겁니다.

#include <cstdio>
#include <algorithm>
using namespace std;
int M,N,map[1001][1001],dp[1001][1001];
int main(){
    scanf("%d%d",&M,&N);
    for(int i=1;i<=M;i++)
        for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
    int ans=0;
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            if(!map[i][j]){
                if(!dp[i-1][j-1] || !dp[i][j-1]|| !dp[i-1][j]) dp[i][j]=1;
                else dp[i][j]=min(min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;
                ans=max(ans,dp[i][j]);
            }
        }
    }
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] 이분 탐색

[풀이]
구간을 몇개로 나누어야 하는지, 어디를 기준으로 나누어야 하는지를 찾으려고 하면 N 제한이 5000이므로
무리가 있습니다.

이런 방법들 대신에 최종적으로 구해야하는 답인 "구간의 점수의 최댓값의 최솟값"에서 "구간의 점수의 최댓값" 을 어떤 수 m으로 고정해놓고 구간을 나눠보는 방식을 사용할 수 있습니다.

어떤 구간의 점수도 m 이상이 되도록 구간을 나누었을 때, 총 구간의 개수가 M 이하라면 이 m의 값은 정답이 될수도 있는 값이지만 최솟값은 아닙니다. 이 m의 값을 조금씩 줄여가면서 답이 될 수 있는지 확인해보는 이분탐색을 이용하면
시간내에 최적의 m 값을 찾을 수 있습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[5001];
bool check(int m){
    int cnt=0;
    int minv=a[0],maxv=a[0];
    for(int i=0;i<=N;i++){
        minv=min(minv,a[i]);
        maxv=max(maxv,a[i]);

        int diff = maxv-minv;
        if(diff<=m) continue;
        cnt++;

        minv=maxv=a[i];
    }
    return cnt<=M;
}
int sol(){
    int lo=-1,hi=10000;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        if(check(mid)) hi=mid;
        else lo=mid;
    }
    return hi;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    a[N]=1e5;
    printf("%d",sol());
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
인접리스트를 만들 때 vector 대신 set을 이용하면
방문하지 않은 자식 노드들 중에 입력으로 주어진 다음에 방문해야 하는 노드가
있는지를 쉽게 파악할 수 있습니다.
노드가 존재한다면 그 노드를 set에서 제거해주고 다음 노드로 방문해주면 됩니다.

#include <cstdio>
#include <set>
using namespace std;
int idx,N,a[100001];
set<int> adj[100001];
int dfs(int prev,int n){
    idx++;
    if(adj[n].find(prev) != adj[n].end()) adj[n].erase(prev);
    while(!adj[n].empty()){
        int v = a[idx];
        if(adj[n].find(v) == adj[n].end()) return 0;
        adj[n].erase(v);
        bool ret = dfs(n,v);
        if(!ret) return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].insert(v);
        adj[v].insert(u);
    }
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    printf("%d",dfs(0,1));
}

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