프로그래밍

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=391&sw_prbl_sbms_sn=18559

[난이도] level3
[유형] 분할정복

[풀이]
N 제한이 굉장히 크기 때문에 일일이 계산해주면 안되고 재귀함수를 이용한 분할정복을 해주어야 합니다.

#include <cstdio>
using ll = long long;
ll K,P,N,mod=1000000007;
ll sol(ll n){
    if(n==1) return P;
    ll ret = sol(n/2);
    ret=(ret*ret)%mod;
    if(n%2) ret=(ret*P)%mod;
    return ret;
}
int main(){
    scanf("%lld%lld%lld",&K,&P,&N);
    printf("%lld",(sol(N*10)*K)%mod);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/수퍼바이러스.cpp

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

[난이도] Gold5
[유형] 분할정복

[풀이]
지문 이해가 어려운 문제였습니다.
b^-1 이 역원이라는것을 인지한 뒤로 b^x 꼴의 수를 거듭제곱수라고 머릿속에서 생각하지 않게되어
b^x-2이 단순한 b의 x-2 제곱수라는것을 생각하지 못하였습니다.

b^-1을 직접 구하려다 실패하고 풀이를 보고 b^x-2를 구하면 되는 문제라는 것을 알게되었습니다.
x가 1000000005 제곱을 해야하기 때문에 직접 곱하면 안되고 재귀를 이용한 분할정복을 이용하였습니다.

import java.util.*
val bw = System.`out`.bufferedWriter()
val mod = 1000000007
fun gcd(pa:Long,pb:Long):Long{
    var a = pa
    var b = pb
    if(a>b) a = b.also{b=a}
    while(a>0){
        var c = b%a
        b = a
        a = c
    }
    return b
}
fun sol(n:Int,k:Long):Long{
    if(n==1) return k
    var ret = 1L
    if(n%2==1) ret=k
    var v = sol(n/2,k)
    v = (v*v)%mod
    return (ret*v)%mod
}
fun main() = with(System.`in`.bufferedReader()){
    var M = readLine().toInt()
    var ans = 0L
    repeat(M){
        val (a,b) = readLine().split(' ').map{it.toLong()}
        ans += when{
            a%b==0L -> (a/b).toLong()
            else -> {
                var g = gcd(a,b)
                var down = (a/g).toLong()
                var up = (b/g).toLong()
                down = sol(mod-2,down)
                down*up
            }
        }
        ans%=mod
    }
    println(ans)
}

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

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

[난이도] level2
[유형] 분할정복

[풀이]
정사각형의 수가 모두 같지 않다면 4개로 분할된 정사각형을 다시 검사하도록
재귀함수를 호출해주고 모두 같다면 0,1인지에 따라 개수를 1개 더해줍니다.

#include <string>
#include <vector>
using namespace std;
vector<int> answer(2);
vector<vector<int>> arr;
int same(int y,int x,int n){
    int t = arr[y][x];
    for(int i=y;i<y+n;i++)
        for(int j=x;j<x+n;j++)
            if(t!=arr[i][j]) return -1;
    return t;
}
void sol(int y,int x,int n){
    int ret = same(y,x,n);
    if(ret!=-1){
        answer[ret]++;
        return;
    }    
    int b = n/2;
    sol(y,x,b);
    sol(y+b,x,b);
    sol(y,x+b,b);
    sol(y+b,x+b,b);
}

vector<int> solution(vector<vector<int>> _arr) {
    arr=_arr;
    sol(0,0,arr.size());
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/쿼드압축 후 개수 세기.cpp

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

[난이도] Silver1
[유형] 분할정복

[풀이]
A를 B번 곱해야 하는데 B의 범위가 int의 최댓값 까지이므로 직접 곱해서는
시간내에 해결이 불가능합니다.
그러므로 A^2n = A^n*A^n인 거듭제곱의 성질을 이용한 분할정복으로 문제를 해결할 수 있습니다.

각 재귀 호출 sol(n)에서 sol(n/2)을 호출하여 이 값을 제곱해주고
만약 n이 홀수인경우 이 값에 A를 추가로 한번 더 곱해준 값을
리턴해주면 O(lgN)의 시간복잡도로 답을 구할 수 있습니다.

A의 최댓값 역시 int의 최댓값 까지이므로 연산시 오버플로우 방지를 위해 long long 자료형을 이용하였습니다.

#include <cstdio>
using ll = long long;
ll A,B,C;
ll sol(ll n){
    if(n==1) return A; 
    ll ret = sol(n/2);
    ret = (ret*ret)%C;
    if(n%2) ret=(ret*A)%C;
    return ret;
}
int main(){
    scanf("%lld%lld%lld",&A,&B,&C);
    printf("%lld",sol(B)%C);
}

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

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

[난이도] Gold4
[유형] 분할정복

[풀이]
preorder 배열에서는 맨 앞의 원소가 root이다.
inorder 배열에서 root값을 찾으면 그 root값을 기준으로 좌측이 left child, 우측이 right child이다.
이 성질을 이용하여, 재귀함수로 left child, right child의 preoder,inorder 각각의 배열에서의 범위를 전달하는 방식으로 답을 구한다.

#include <cstdio>
int tc,N,pre[1001],in[1001];
void post(int lp,int rp,int li,int ri){
    if(lp>rp) return;
    if(lp==rp) {
        printf("%d ",pre[lp]);
        return;
    }

    int root = pre[lp];
    int idx=li;

    for(int i=li;i<=ri;i++){
        if(root==in[i]){
            idx=i;
            break;
        }
    }
    int lcnt = idx-li;

    post(lp+1,lp+lcnt,li,idx-1);
    post(lp+lcnt+1,rp,idx+1,ri);
    printf("%d ",pre[lp]);
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&pre[i]);
        for(int i=0;i<N;i++) scanf("%d",&in[i]);
        post(0,N-1,0,N-1);
        puts("");
    }
}

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