프로그래밍

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

[난이도] Silver2
[유형] DP

[풀이]
재귀만을 이용해서 값을 구하게 되면 w(x,y,z)를 중복으로 실행하는 경우가 여러번 생길 수 있으므로
DP[21][21][21] 배열을 선언하여 메모제이션을 해주어야 한다.
DP[x][y][z]에 값이 있으면 이 값을 return해서 더이상 재귀가 수행되지 않도록 한다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max
import java.lang.Integer.min
import java.util.*
var dp=Array(21,{Array(21,{Array<Int>(21,{-1})})})
fun sol(n:Int,m:Int,k:Int):Int{
    when {
        (n <= 0 || m <= 0 || k <= 0) -> return 1
        (n > 20 || m > 20 || k > 20) -> return sol(20, 20, 20)
    }
    if(dp[n][m][k]!=-1) return dp[n][m][k]
    dp[n][m][k] = when{
        (n<m&&m<k)->sol(n,m,k-1)+sol(n,m-1,k-1)-sol(n,m-1,k)
        else -> sol(n-1,m,k)+sol(n-1,m-1,k)+sol(n-1,m,k-1)-sol(n-1,m-1,k-1)
    }
    return dp[n][m][k]
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    while(true){
        var (N,M,K) = readLine().split(' ').map{it.toInt()}
        if(N==-1&&M==-1&&K==-1) break
        println("w($N, $M, $K) = ${sol(N,M,K)}")
    }
}

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

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

[난이도] Silver2
[유형] 백트래킹

[풀이]
N제한이 10밖에 안되기 때문에 순회할 수 있는 모든 경우를 백트래킹 해주면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min
import java.util.*
var N=0
val cost = Array(10,{Array(10){0}})
val visit = Array(10){false}
var ans=987654321
fun sol(start:Int,n:Int,sum:Int,cnt:Int){
    visit[n]=true
    //println("n:${n}, sum:${sum}, cnt:${cnt}")
    if(cnt==N && cost[n][start]>0){
        ans=min(ans,sum+cost[n][start])
    }
    for(i in 0 until N){
        if(cost[n][i]>0 && !visit[i]){
            sol(start,i,sum+cost[n][i],cnt+1)
        }
    }
    visit[n]=false
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    N=readLine().toInt()
    for(i in 0 until N){
        var ip = readLine().split(' ').map{it.toInt()}
        for(j in 0 until N) cost[i][j]=ip[j]
    }
    for(i in 0 until N) {
        sol(i,i, 0, 1)
    }
    println(ans)
}

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

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

[난이도] Silver2
[유형] DFS

[풀이]
간단한 DFS 문제

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
val mxN = 250000
var Primes = Array(mxN+1){true}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    for(i in 2..mxN/2){
        if(!Primes[i]) continue
        for(j in i*2..mxN step i) Primes[j] = false
    }
    while(true){
        var k=readLine().toInt()
        if(k==0) break
        var ans = 0
        for(i in k+1..2*k) if(Primes[i]) ans++
        println(ans)
    }
}

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

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

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

[풀이]
에라토스테네스의 체

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
val mxN = 250000
var Primes = Array(mxN+1){true}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    for(i in 2..mxN/2){
        if(!Primes[i]) continue
        for(j in i*2..mxN step i) Primes[j] = false
    }
    while(true){
        var k=readLine().toInt()
        if(k==0) break
        var ans = 0
        for(i in k+1..2*k) if(Primes[i]) ans++
        println(ans)
    }
}

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

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

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

[풀이]
stack을 이용해 0이면 pop, 아니면 push를 해주고 스택에 남은 모든 원소를 더하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var k = readLine().toInt()
    var st = Stack<Int>()
    while(k-->0){
        var ip = readLine().toInt()
        when(ip){
            0 -> st.pop()
            else -> st.push(ip)
        }
    }
    var ans = 0
    while(!st.empty()) ans += st.pop()
    println(ans)
}

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

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

[난이도] Silver3
[유형] 투 포인터

[풀이]
값들을 배열에 저장 후 sum과 left index를 의미하는 left 변수를 유지하면서
for문을 돌리면서 sum에 arr[i]를 더해준다.
더해준 뒤 sum이 m보다 크다면 arr[l]을 sum에서 빼주고 l을 1 증가시켜주기를 sum이 m보다 크지 않을때까지 반복한다.
위 과정을 끝낸 뒤 sum==m 이라면 ans에 1을 더해주고 다음으로 넘어간다.

import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var input = readLine().split(' ')
    var n = input[0].toInt()
    var m = input[1].toInt()
    var arr = readLine().split(' ').map{it.toInt()}
    var ans=0
    var sum=0
    var l=0
    for(i in 0..arr.size-1) {
        sum += arr[i]
        if (sum > m) {
            while (l < i && sum > m) sum -= arr[l++]
        }
        if(sum == m) ans++
    }
    println(ans)
}

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

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

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

[풀이]
N이 8만으로 N^2 풀이는 불가능하므로 스택을 이용해서 풀어야 한다.

0번 건물의 index부터 차례로 stack에 집어넣으면서 stack에 들어있는 건물의 높이가 내림차순이 되도록 유지한다.
내림차순이 되게 하려면 스택의 top인 건물이 현재 확인중인 i번 건물보다 낮아질때까지 pop을 해줘야 한다.
pop 되어야할 i보다 낮은 k번 건물은 i-k-1 만큼의 건물을 볼수 있다. (k~i-1 까지 내림차순인 것이 보장되므로)
그러므로 pop할때마다 ans에 i-k-1만큼을 더해주면 ans가 답이다.

N이 80000이고 건물이 모두 내림차순으로 되어있다면 정답이 int 범위를 넘어가므로 long long을 사용해야 한다.

#include <cstdio>
#include <stack>
using namespace std;
int N,h[80001];
long long ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&h[i]);
    h[N]=2e9;
    stack<int> st;
    for(int i=0;i<=N;i++){
        while(!st.empty() && h[st.top()] <= h[i]){
                ans+=i-st.top()-1;   
                st.pop();
        }
        st.push(i);
    }
    printf("%lld",ans);
}

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

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

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

[풀이]
N이 1일때부터 하나씩 확인해보면
1 2 3 4 5 6 7 8 9 10 11 12 13 14
SK CY SK SK SK SK CY SK CY SK SK SK SK CY

와 같이 7을 주기로 반복되며 나머지가 2,0인 경우에만 CY인 것을 알수 있다.

#include <cstdio>
long long N;
int main(){
    scanf("%lld",&N);
    puts(N%7==2||N%7==0?"CY":"SK");
}

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