프로그래밍

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

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

[풀이]
최대공약수 구하기
답이 int 범위를 넘어갈 수 있으므로 Long으로

import java.io.BufferedReader
import java.io.InputStreamReader
fun gcd(n:Int,m:Int):Int{
    var a=n
    var b=m
    if(a>b) a=b.also{b=a}

    while(a>0){
        var c = b%a
        b=a
        a=c
    }
    return b
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var t = readLine().toInt()
    val arr = IntArray(101)
    while(t-->0){
        val ip=readLine().split(' ')
        val N=ip[0].toInt()
        for(i in 1..N) arr[i-1]=ip[i].toInt()
        var ans:Long=0
        for(i in 0 until N-1){
            for(j in i+1 until N){
                ans+=gcd(arr[i],arr[j])
            }
        }
        println(ans)
    }
}

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

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

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

[풀이]
nCm 은 n!/(m!x(n-m)!) 로 표현된다.

문제 https://www.acmicpc.net/problem/1676 에서 봤듯이 끝의 0의 개수는 어떤 수를 소인수분해 했을 때 5x2가 몇개나 있는지에 따라 결정된다.
n!/(m!x(n-m)!) 식에서 2와 5가 최종적으로 몇개 남는지를 구하고 둘중 최솟값을 출력하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min
fun get(p:Int,k:Int):Int{
    var cnt=0
    var n=p
    while(n>0){
        n/=k
        cnt+=n
    }
    return cnt
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val ip=readLine().split(' ')
    val N=ip[0].toInt()
    val M=ip[1].toInt()
    val a = get(N,2)-get(N-M,2)-get(M,2)
    val b = get(N,5)-get(N-M,5)-get(M,5)
    println(min(a,b))
}

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

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

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

[풀이]
모든 10은 2x5로 만들어지기 때문에 1~N 모든 수를 소인수 분해 했을 때 2와 5의 개수 중의 최솟값이 답이다.
항상 5가 더 적은 것이 보장되기 때문에 5의 개수만 구하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val N=readLine().toInt()
    var cnt:Int=0
    for(i in 1..N) {
        var j=i
        while(j>0 && j%5==0){
            cnt++
            j/=5
        }
    }
    println(cnt)
}

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

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

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

[풀이]
에라토스테네스의 체를 이용해 소수를 미리 구해준다

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.IndexOutOfBoundsException
import java.util.*
const val mxN = 1000000
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    var list = ArrayList<Int>()
    var nP = BooleanArray(mxN+1)
    nP[1]=true

    for(i in 2..mxN/2){
        if(nP[i]) continue
        var j=i*2
        while(j<=mxN){
            nP[j]=true
            j+=i
        }
    }
    for(i in 2..mxN) {
        if(!nP[i]) list.add(i)
    }
    while(true){
        var ip = readLine().toInt()
        if(ip==0) break

        for(a in list){
            if(!nP[ip-a]){
                println("$ip = $a + ${ip-a}")
                break;
            }
        }
    }
}

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

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

[난이도] Silver2
[유형] 에라토스테네스의 체

[풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var ip = readLine().split(' ')
    var n=ip[0].toInt()
    var m=ip[1].toInt()
    var notPrime = BooleanArray(1000001)
    notPrime[1]=true
    for(i in 2..m){
        if (notPrime[i]) continue
        var j = i*2
        while(j<=m){
            notPrime[j]=true
            j+=i
        }
    }
    for(i in n..m) if(!notPrime[i]) println(i)
}

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

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

[난이도] Silver3
[유형] 스택

[풀이]
스택 문제이지만 스택을 사용하지 않아도 해결이 가능하다.

0~N-1 문자를 순회하면서
1) s[i]가 '(' 인 경우 s[i+1]이 ')' 이면 레이저이고 아니면 쇠막대기의 왼쪽끝이다.
쇠막대기인 경우, 현재 쌓여있는 막대 개수 cnt를 1 증가시켜준다
레이저인 경우, 현재 쌓인 막대기만큼 ans에 더해주고 index를 한칸 넘어간다 ( ')'를 스킵해야 하므로 )

2) s[i]가 ')' 인 경우
막대가 끝났으므로 cnt를 1 감소시키고
ans에 1을 더해준다. 왜나하면 막대의 맨 오른쪽 조각을 더해줘야 하므로

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var s = readLine()
    var cnt=0
    var ans=0
    var i=0
    while(i<s.length){
        when(s[i]){
            '('->{
                if(s[i+1]==')') {
                    ans+=cnt
                    i++
                }
                else cnt++
            }
            else->{
                ans++
                cnt--
            }
        }
        i++
    }
    println(ans)
}

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

[20210510] 큐
[BOJ/백준][Silver4] 10845 : 큐 (Kotlin)

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

[난이도] Silver4
[유형] 큐

[풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    var q:Queue<Int> = LinkedList<Int>()
    while(n-->0){
        var ip=readLine().split(' ')
        when(ip[0]){
            "push"->q.add(ip[1].toInt())
            "pop"-> println(if(q.isEmpty()) -1 else q.poll())
            "empty"->println(if(q.isEmpty()) 1 else 0)
            "front"->println(if(q.isEmpty()) -1 else q.peek())
            "back"->println(if(q.isEmpty()) -1 else q.last())
            else->println(q.size)
        }
    }
}

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

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

[난이도] Silver4
[유형] 큐

[풀이]

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine().toInt()
    var q:Queue<Int> = LinkedList<Int>()
    while(n-->0){
        var ip=readLine().split(' ')
        when(ip[0]){
            "push"->q.add(ip[1].toInt())
            "pop"-> println(if(q.isEmpty()) -1 else q.poll())
            "empty"->println(if(q.isEmpty()) 1 else 0)
            "front"->println(if(q.isEmpty()) -1 else q.peek())
            "back"->println(if(q.isEmpty()) -1 else q.last())
            else->println(q.size)
        }
    }
}

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