프로그래밍

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

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

[풀이]
어떤 건물 i에서 j를 볼 수 있으려면 i+1~j-1 인 어떤 모든 k에 대해
i,j의 기울기가 i,k의 기울기보다 커야한다.
i,j를 볼 수 있다는 것은 j에서도 i를 볼 수 있다는 것이다.
2중 for문으로 모든 i,j 짝에 대해 볼 수 있는지 확인할 수 있다.

#include <cstdio>
int N,a[50],ans,c[50];
double getD(int i,int j){
    return (a[j]-a[i])/(double)(j-i);
}
int main(){ 
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N-1;i++){
        double cur,d;
        for(int j=i+1;j<N;j++){
            d = getD(i,j);
            if(j-1==i || cur < d){
                cur = d;
                c[i]++; c[j]++;
            }
        }
    }
    for(int i=0;i<N;i++) if(ans < c[i]) ans=c[i];
    printf("%d",ans);
}

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

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

[난이도] Gold4
[유형] Map, Trie

[풀이]
종의 이름을 key로 하는 (string,int) pair의 map을 만들어서
해당 종의 총 갯수를 구하면 된다.

나무 이름에 공백이 있을 수도 있으므로 한줄 전체를 입력으로 받아야 한다.
getline(cin,s) 함수를 이용하면 한줄을 단위로 입력받을 수 있다.
EOF 같은 경우 아래와 같이 처리해주면 파일이 끝날 때 while문을 빠져나가게 된다.
while(getline(cin,s)){

}

Trie로 풀면 더 빠른시간내에 해결할 수 있다고 한다.

#include <iostream>
#include <map>
#include <string>
#include <cmath>
using namespace std;
map<string,int> m;
int n;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    while(getline(cin,s)){
        m[s]++;
        n++;
    }
    for(auto k : m){
        double b = 100*k.second / (double)n;
        printf("%s %.4lf\n",k.first.c_str(),b);
    }
}

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

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

[난이도] Gold4
[유형] 재귀

[풀이]
재귀함수를 이용해 left와 right 자식의 높이를 비교해서 낮은 쪽이 높은 쪽과 같아지도록 수정한다.

#include <cstdio>
int k,last,a[1<<21];
long long ans;
int sol(int n){
    if((1<<k)-1 <= n && n < last) return 0;
    int l = sol(n*2+1),r = sol(n*2+2);
    if(a[n*2+1]+l<a[n*2+2]+r) a[n*2+1] = a[n*2+2]+r-l;
    else a[n*2+2] = a[n*2+1]+l-r;
    ans += a[n*2+2]+a[n*2+1];
    return l+a[n*2+1];
}
int main(){
    scanf("%d",&k);
    last = (1<<(k+1))-1;
    for(int i=1;i<last;i++) scanf("%d",&a[i]);
    sol(0);
    printf("%lld",ans);
}

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

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

[난이도] Gold4
[유형] DFS

[풀이]
무방향 그래프의 cycle을 찾는 문제이다.
next node가 이미 방문한 node이면서 부모가 아니면 cycle이다.
부모를 체크하기 위해 visit 배열에 방문한 순서를 저장해놓고
현재 노드의 visit, 다음 노드의 visit 차가 1이면 부모 노드이므로 무시한다.

#include <cstdio>
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
char map[50][50];
int visit[50][50];
bool dfs(int y,int x,int k){
    visit[y][x]=k;
    for(int i=0;i<4;i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(ny < 0 || nx < 0|| ny >=N || nx >= M || map[ny][nx]!=map[y][x]) continue; 
        if(visit[ny][nx]){
            if(k-visit[ny][nx]>1) return 1;
        } else if(dfs(ny,nx,k+1)) return 1;
    }
    return 0;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf(" %c",&map[i][j]);  
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!visit[i][j]){
                if(dfs(i,j,0)){
                    puts("Yes");
                    return 0;
                }
            }
        }
    }
    puts("No");
}

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

www.acmicpc.net/problem/10986

[난이도] Gold4
[유형] 누적합

[풀이]
(i,j) 구간합이 M으로 나누어 떨어지는 경우는
sum(1,j)%M == sum(1,i-1)%M 인 경우이다.

a[1]+a[2]...a[i-1]+a[i]+a[i+1]....a[j]

왜냐하면 j까지의 합이 위와 같고

만약 sum(1,i-1)%M가 k 일때, sum(1,j)%M도 k이려면
sum(i,j)%M은 0이어야 한다.

결국 정답은 나머지가 똑같은 누적합 중에서 두개를 뽑는 경우의 수이다.

#include 
int N,M,cnt[1001],sum[1000001];
long long ans;
int main(){
    scanf("%d%d",&N,&M);
    cnt[0]++;
    for(int i=1;i<=N;i++) {
        int v;
        scanf("%d",&v);
        sum[i] = (sum[i-1]+v)%M;
        cnt[sum[i]]++;
    } 
    for(int i=0;i<m;i++){ class="hljs-keyword" <span="">int n = cnt[i];
        if(n>1) ans+= ((long long)n*(n-1))/2;
    }
    printf("%lld",ans);
}</m;i++){>

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

www.acmicpc.net/problem/2643  

[난이도] Gold4

[유형] DP

[풀이]

2차원 LIS 문제이다.

정렬 이후 DP로 해결할 수 있다.

점화식 :

dp[n] = max(dp[i]); (n+1 <= i <= N)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int u,v;
};
int N,dp[101];
P a[101];
bool cmp(P& a,P& b){
    if(a.u > b.u) return 1;
    else if(a.u==b.u) return a.v > b.v;
    return 0;
}
int sol(int n){
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret = 0;
    for(int i=n+1;i<=N;i++) if(a[i].v <= a[n].v) ret = max(ret,sol(i));
    return ret += 1;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u<v) swap(u,v);
        a[i].u=u, a[i].v=v;
    }
    a[0].u=a[0].v=9e8;
    sort(a,a+N+1,cmp);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0)-1);
}

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

www.acmicpc.net/problem/2457  

[난이도] Gold4

[유형] Greedy

[풀이]

pair vector를 만들어서 first에 꽃이 피는날 second에 꽃이 지는날을 저장 후 정렬.

0~N-1 루프를 돌면서 최적의 꽃을 찾아주면 된다.

코드에서 s는 현재까지 꽃이 무조건 피어있다고 보장되는 날이다.

first가 s이하인 꽃들 중에서 second가 가장 큰 값을 mxr에 갱신해서 찾는다.

first가 s를 넘어가게 되면 위의 mxr이 최대인 꽃을 선택하고 다음 꽃을 찾는다.

이 때, 꽃이 피어있다고 보장되는나 s는 mxr로 갱신시킨다.

위의 과정을 반복하면 된다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[] = {0,31,28,31,30,31,30,31,31,30,31,30,31},base[13];
int N,ans;
vector<pair<int,int>> v;
int main(){
    for(int i=1;i<=12;i++) base[i]=a[i-1]+base[i-1];
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int b[4];
        for(int j=0;j<4;j++) scanf("%d",&b[j]);
        v.push_back({base[b[0]]+b[1],base[b[2]]+b[3]});
    }
    sort(v.begin(),v.end());

    int s=base[3]+1,e=base[11]+30,mxr=-1,ok=0;
    for(int i=0;i<N;i++){
        auto p = v[i];
        int l=p.first,r=p.second;
        if(l<=s) {
            mxr=max(r,mxr);
            if(mxr > e){
                ok=1;
                ans++;
                break;
            }
        }
        else {
            if(mxr==-1) break;
            ans++;
            s=mxr;
            mxr=-1;
            i--;
        }
    }
    printf("%d",ok?ans:0);
}

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

www.acmicpc.net/problem/1695

[난이도] Gold4

[유형] DP

[풀이]

top-down dp로 해결할 수 있다.

sol(l,r) : 왼쪽 index가 l, 오른쪽이 r일때 팰린드롬을 만들기 위해 추가해야되는 숫자의 개수.

점화식

case l==r : sol(l,r) = sol(l+1,r-1)

case l!=r : sol(l,r) = min(sol(l,r-1)+sol(l+1,r))

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[5000],dp[5000][5000];

int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret !=-1) return ret;
    if(a[l]==a[r]) ret = sol(l+1,r-1);
    else ret = min(sol(l,r-1),sol(l+1,r))+1;
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,n-1));
}

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