프로그래밍

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://www.acmicpc.net/problem/11660

[난이도] Silver1
[유형] DP

[풀이]
입력을 받으면서 sum[i][j]에 (1,1)~(i,j)까지의 합을 저장합니다.
현재 입력은 (i,j)의 값이 r[j-1]일때, sum[i][j]는 아래와 같이 구할 수 있습니다.
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+r[j-1]
sum[i-1][j-1]이 두번 두해졌기 때문에 한번 빼는 것입니다.

쿼리 (x1,y1)~(x2,y2) 은 아래와 같이 구할 수 있습니다.
sum[y2][x2]-sum[y1-1][x2]-sum[y2][x1-1]+sum[y1-1][x1-1]
이번엔 반대로 sum[y1-1][x1-1]이 두번 빠졌으므로 한번 더해주는 것입니다.

println을 사용하면 시간초과가 나서 bufferedWriter를 이용해야 했습니다.

import java.util.*
val bw = System.`out`.bufferedWriter()
var sum = Array(1025){IntArray(1025)}
fun main() = with(System.`in`.bufferedReader()){
    val (N,M) = readLine().split(' ').map{it.toInt()}
    for(i in 1..N){
        val r = readLine().split(' ').map{it.toInt()}
        for(j in 1..N)  sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+r[j-1]
    }
    repeat(M){
        val (y1,x1,y2,x2) = readLine().split(' ').map{it.toInt()}
        val ret = sum[y2][x2]-sum[y1-1][x2]-sum[y2][x1-1]+sum[y1-1][x1-1]
        bw.write(ret.toString()+'\n')
    }
    bw.flush()
}

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

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

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

[풀이]
nCm 공식을 적용하여 분자, 분모를 각각 계산한 뒤 분자/분모를 해준것이 정답입니다.
n,m이 100 제한이라 unsigned long 범위도 넘어가므로 BigInteger를 이용해야 합니다.
C++같이 BigInteger를 지원하지 않는 경우에는 String을 통한 덧셈 연산으로 해결해야 합니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.math.BigInteger
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N,M) = readLine().split(' ').map{it.toInt()}
    var up = BigInteger("1")
    var down = BigInteger("1")
    for(i in 1..M){
        up = up.multiply(BigInteger((N-i+1).toString()))
        down = down.multiply(BigInteger(i.toString()))
    }
    println(up.divide(down))
}

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

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

[난이도] Silver1
[유형] 트리

[풀이]
Preorder, Inorder, Postorder 순회를 구현할 수 있는지를 묻는 문제입니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var N = 0
var a = Array<Pair<Int,Int>>(26){Pair(0,0)}
fun preorder(n:Int){
    if(n==-1) return
    print('A'+n)
    preorder(a[n].first)
    preorder(a[n].second)
}

fun inorder(n:Int){
    if(n==-1) return
    inorder(a[n].first)
    print('A'+n)
    inorder(a[n].second)
}

fun postorder(n:Int){
    if(n==-1) return
    postorder(a[n].first)
    postorder(a[n].second)
    print('A'+n)
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    N = readLine().toInt()
    repeat(N){
        val carr = readLine().split(' ').map{it[0]}
        var left = if(carr[1]=='.') -1 else carr[1]-'A'
        var right = if(carr[2]=='.') -1 else carr[2]-'A'
        a[carr[0]-'A'] = Pair(left,right)
    }
    preorder(0)
    println()
    inorder(0)
    println()
    postorder(0)
}

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

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
val dimen2 = Array(101){IntArray(101)} // 2차원
val dimen3 = Array(101){Array(101){IntArray(101)} } // 3차원
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    println("초기값 : ${dimen3[100][3][2]}") // 0
    dimen3[100][3][2]=12
    println(dimen3[100][3][2]) // 12
}

코틀린에서는 C++에서처럼

int dimen2[100][100] 이런식으로 간단하게 배열 선언이 불가능합니다.

 val dimen2 = Array(101){IntArray(101)} 

그래서 위와 같은 방법을 이용합니다.

IntArray(101)은 Java의 Primitive 타입 배열 new int[101] 과 동일한 배열을 생성하며

이것을 101개 생성하는것이 Array(101){IntArray(101)}  입니다.

101개를 모두 IntArray(101)로 초기화 하겠다는 의미입니다.

Array<IntArray> 타입인데 타입추론을 해주므로 <IntArray>는 생략해도 됩니다.

3차원배열을 선언할때도 동일하게 선업하면 됩니다. 

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

[난이도] Div.2
[유형] Greedy

[풀이]
폰의 앞이 비어있다면 무조건 앞으로 전진이 가능하기 때문에
폰이 있으면 앞이 비어있는 폰은 빼주면서 정답에 이 폰의 개수를 더해줍니다.

그다음 좌측 폰부터 확인하면서
좌측 윗쪽에 폰이 있다면 이쪽으로 먼저 보내주고, 없으면 우측 윗쪽에 폰이 있는지 체크해서
폰이 있으면 이쪽으로 보내고 정답에 1을 더해줍니다.

좌측부터 검사하기 때문에 대각선 앞의 적 폰이 있는지 검사할 때 좌측->우측 순으로 검사해서 사용해 주는것이 제일 유리합니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;

int tc,N;
string me,enemy;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> tc;
    while(tc--){
        cin >> N >> enemy >> me;

        int ans=0;
        for(int i=0;i<N;i++){
            if(enemy[i]=='0' && me[i]=='1'){
                ans++;
                me[i]='0';
            }
        }

        for(int i=0;i<N;i++){
            if(me[i]=='0') continue;
            if(i!=0 && enemy[i-1]=='1'){
                ans++;
                continue;
            }
            if(i!=N-1 && enemy[i+1]=='1'){
                ans++;
                enemy[i+1]='0';
            }
        }
        cout << ans << '\n';
    }
}

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

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

[난이도] Div.2
[유형] 수학

[풀이]
P가 소수일 때, P mod a=P mod b 를 만족하는 a,b를 찾는 문제입니다.
P가 소수이면 P-1은 반드시 1이외의 약수가 존재할 것이라는 생각으로
P-1의 약수를 찾는 O(루트N) 알고리즘을 적용하여
P-1의 약수중 가장 작은 수와 P-1을 출력해서 AC를 받았습니다.

컨테스트 종료 후 튜토리얼을 보니 P-1은 당연히 짝수이니 2와 P-1을 출력해주면 되는
훨씬 간단한 문제였습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <map>
using namespace std;
using ll = long long;

int tc,P;

int sol(int p){

    for(int i=2;i<=sqrt(p);i++){
        if(p%i==0){
            return i;
        }
    }
    return 0;
}

int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&P);
        printf("%d %d\n",sol(P-1),P-1);
    }

}

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

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

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

[풀이]
n 1개로 무조건 n을 만들 수 있기 때문에 answer의 값은 1부터 시작합니다.
1~n-1을 순회하면서 i+(i+1)+(i+2)... 값을 만들어보면서 n이 넘어가면 break,
n이 나오면 answer에 1을 추가하고 break 하는식으로 답을 구해가면 됩니다.

n이 10000이고 i가 1인 경우에도
1+2+3+4.... = (n*(n+1))/2 = 10000 (등차수열 공식)
을 만족하려면 더하는 횟수인 n이 대충 계산해도 150도 넘을 수 없다는 것을 알 수 있습니다.
그러므로 시간복잡도는 O(10000*150) 정도로 시간내에 해결이 가능합니다.

#include <string>
#include <vector>
using namespace std;
int solution(int n) {
    int answer=1;
    for(int i=1;i<n;i++){ 
        bool ok=0;
        int sum=i,cur=i;
        while(sum<n){
            sum+=++cur;
            if(sum==n){
                answer++;
                break;
            }
        }
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/숫자의 표현.cpp