프로그래밍

www.acmicpc.net/problem/10830

[난이도] Gold4

[유형] Divide and Conquer(행렬곱)

[풀이]

1. 구조체 A를 정의하고 연산자 오버로딩을 이용해서 행렬곱 구현. 2. A^2n=A^n*A^n인 행렬의 성질을 이용하여 재귀함수로 정답 도출

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
using vv = vector<vector<ll>>;
int N;
ll B,mod=1000;
struct A{
    vv arr;
    A(){};
    A(vv arr):arr(arr){};
    A operator*(A& a){
        vv tmp = arr;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                tmp[i][j]=0;
                for(int k=0;k<N;k++){
                    tmp[i][j] += arr[i][k]*a.arr[k][j];
                    tmp[i][j]%=mod;
                }
            }
        }
        return A(tmp);
    }
};
A base;
void print(A& a){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            printf("%lld ",a.arr[i][j]);
        }
        puts("");
    }
}
A sol(ll n){
    if(n==1) return base;
    A u = sol(n/2);
    u=u*u;
    if(n%2) u=u*base;
    return u;
}
int main(){
    scanf("%d%lld",&N,&B);
    vv v;
    v.resize(N);
    for(int i=0;i<N;i++){
        ll t;
        for(int j=0;j<N;j++){
            scanf("%lld",&t);
            v[i].push_back(t%mod);
        }
    }
    base = A(v);
    A ret = sol(B);
    print(ret);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/10830.cpp

www.acmicpc.net/problem/1043

[난이도] Gold4

[유형] DFS

[풀이]

지민이는 진실을 아는 사람이 있는 파티에서는 거짓말을 못한다. 어떤 파티에서 진실을 아는 사람이 있어서 진실을 말하면 그 파티에 참여한 진실을 모르는 사람이 참여한 모든 파티에서도 거짓말을 할 수 없다. 즉, 지민이가 진실을 말한 파티에 있는 모든 사람들은 진실을 아는거나 마찬가지이다. 이 성질을 이용하여 진실을 아는 사람들을 DFS를 이용하여 갱신해주면 답을 구할 수 있다.

#include <cstdio>
#include <vector>
using namespace std;
int N,M;
vector<int> pp[51],pty[51],tp;
bool visit[51];
void dfs(int n){
    visit[n] = 1;
    for(auto ptn : pp[n]){
        for(auto p : pty[ptn]){
            if(!visit[p]) dfs(p);
        }
    }
}
int main(){
    scanf("%d%d",&N,&M);
    int t,v;
    scanf("%d",&t);
    for(int i=0;i<t;i++) {
        scanf("%d",&v);
        tp.push_back(v);
    }
    for(int i=1;i<=M;i++){
        scanf("%d",&t);
        for(int j=0;j<t;j++){
            scanf("%d",&v);
            pty[i].push_back(v);
            pp[v].push_back(i);
        }
    }

    for(auto a : tp) dfs(a);
    int ans = 0;
    for(int i=1;i<=M;i++){
        bool ok = 1;
        for(auto p : pty[i]) {
            if(visit[p]){
                ok = 0;
                break;
            }
        }
        if(ok) ans++;
    }
    printf("%d",ans);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1043.cpp

www.acmicpc.net/problem/1022

[난이도] Gold4

[유형] 구현

[풀이]

소용돌이의 오른쪽 아래 꼭지점은 (2*n+1)^2 라는점을 이용

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int r1,r2,c1,c2;

int getV(int r,int c){

    int a = max(abs(r),abs(c));
    int v = (2*a+1);
    v*=v;
    if(a==r) return v-(a-c);
    v-=2*a;
    if(-a==c) return v-(a-r);
    v-=2*a;
    if(-a==r) return v-(a+c);
    v-=2*a;
    return v-(a+r);
}
int main(){
    scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    int k = 0;
    for(int i=r1;i<=r2;i++){
        for(int j=c1;j<=c2;j++){
            int v = getV(i,j);
            k = max(v,k);
        }
    }

    int t = 0;
    while(k>0){
        t++;
        k/=10;
    }
    for(int i=r1;i<=r2;i++){
        for(int j=c1;j<=c2;j++){
            printf("%*d ",t,getV(i,j));
        }
        puts("");
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1022.cpp

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

[풀이] DP

dp 정의 : dp[n] = n원을 동전으로 교환하는 경우의 수.

 i : 0 ~ K-1까지 모든 동전 종류를 순회하면서

 i 번째 동전까지 썼을때의 dp[j] (j : T~1) 을 구해준다.

 T부터 거꾸로 하는 이유가 중요한데

1부터 할 경우 dp[1~j-1] 이 dp[j] 에 포함될 수 있기 때문이다.

dp[1~j-1]에는 i번째 동전을 쓰는 경우의 수까지 포함되어 있어서 dp[j]에는 포함되면 안된다.

동전 i를 몇개 선택할지 정해야 하기 때문에 동전 개수만큼 순회하면서 sum에 더해주고

if(j-sum >= 0 && dp[j-sum] > 0 을 만족하는 k를 찾으면 dp[j]에 dp[j-sum]을 더해주면 된다.

https://github.com/has2/Algorithm/blob/master/boj/RANDOM_PROBLEM/2624.cpp

https://leetcode.com/problems/battleships-in-a-board/

[풀이] BFS

1XN 또는 NX1 모양의 배를 찾는 문제. 

문제의 조건에 배는 인접하지 않고

valid한 map만 주어진다고 했으므로

BFS를 돌면서 찾은 그룹의 개수가 답이다.

https://github.com/has2/Algorithm/blob/master/leetcode/419.%20Battleships%20in%20a%20Board.cpp

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

https://github.com/has2/Algorithm/blob/master/programmers/level2/%ED%81%B0%20%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

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

[풀이] Greedy

Upperbound를 이용해서 고를 수 있는 범위 내에서 9~0까지 for문을 돌면서 가장 먼저 선택할 수 있는

값을 하나씩 고르면 된다.

https://github.com/has2/Algorithm/blob/master/programmers/level2/%ED%81%B0%20%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

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

[풀이] Greedy

가장 효율적으로 알파벳을 변경하는 방법은 이동시 가장 가까운 곳으로 이동해서 변경해주는 것이다.

어차피 변경해야할 모든 알파벳을 방문해야 하기 때문이다.

어떤 알파벳을 방문할 때 <-,->를 이용하는 두가지 방법 중 min값이 이동거리이다.