프로그래밍

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

[난이도] Silver1
[유형] DP

[풀이]
DP[i] : 카드 i개를 구매하기 위해 지불해야 하는 최솟값

dp[i] = min(dp[i],dp[i-j]+P[i])

#include <cstdio>
#include <algorithm>
using namespace std;
int N,P[1001],dp[1001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&P[i]);
    for(int i=1;i<=N;i++) dp[i]=1e8;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i-j>=0) dp[i]=min(dp[i],P[j]+dp[i-j]);
        }
    }
    printf("%d",dp[N]);
} 

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

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

[난이도] Silver1
[유형] DP

[풀이]
DP[N][M] : N을 M개의 수를 이용해 만들 수 있는 경우의 수.

주의할점 : tc 마다 계산하면 안되고 n=1000,m=1000 일때를 한번 계산해놓으면 모든 케이스를 구할 수 있으므로 재활용하면 된다.

#include <cstdio>
#include <cstring>
int t,n,m,dp[1001][1001],mod = 1e9+9;
int main(){
    scanf("%d",&t);
    dp[1][1]=dp[2][1]=dp[3][1]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            for(int k=1;k<4;k++){
                if(j-k>0) dp[j][i]+=dp[j-k][i-1];
                dp[j][i]%=mod;
            }
        }
    }
    while(t--){
        scanf("%d%d",&n,&m);
        long long ans = 0;
        for(int i=0;i<=m;i++) ans=(ans+dp[n][i])%mod;
        printf("%lld\n",ans);
    }
} 

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

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

[난이도] Silver1
[유형] DP

[풀이]
DP[N][M] : N을 M개의 수를 이용해 만들 수 있는 경우의 수.

#include <cstdio>
#include <cstring>
int t,n,m,dp[1001][1001],mod = 1e9+9;
int main(){
    scanf("%d",&t);
    dp[1][1]=dp[2][1]=dp[3][1]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            for(int k=1;k<4;k++){
                if(j-k>0) dp[j][i]+=dp[j-k][i-1];
                dp[j][i]%=mod;
            }
        }
    }
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d\n",dp[n][m]);
    }
} 

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

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

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

[풀이]
a[1]과 a[N]에 어떤 수가 들어있는지에 따라서 답을 구해야 한다.

최악의 경우는
a[1]에 N, a[N]에 1이 있는 경우, 이 경우에는 1~N-1을 sort -> 2~N을 sorting -> 1~N-1을 sorting 총 3번을 sorting 해야 한다.

이미 정렬이 되어있는 경우 0번

a[1]==1 이거나 a[N]==N인 경우 이것을 제외하고 1번만 정렬하면 되므로 1번

나머지 경우는 2번만 정렬해주면 된다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using ll = long long;
 
int t,N,a[51];
 
int solve(){
    bool ok=1;
    for(int i=1;i<=N;i++){
        if(a[i]!=i){
            ok=0;
            break;
        }
    }
    if(ok) return 0;
    
    if(a[1]==1 || a[N]==N) return 1;
    if(a[1]==N && a[N]==1) return 3;
 
    return 2;
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        printf("%d\n",solve());
    }
}

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

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

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

[풀이]
K와 100-K의 최대공약수를 구한 뒤 100을 최대공약수로 나눠주면 된다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
using namespace std;
using ll = long long;
 
int t,k;
 
int gcd(int a,int b){
    if(a>b) swap(a,b);
 
    while(a>0){
        int c = b%a;
        b=a;
        a=c;
    }
 
    return b;
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&k);
        if(k==100){
            puts("1");
            continue;
        }
 
        int a = k;
        int b = 100-k;
        int g = gcd(a,b);
        printf("%d\n",a/g+b/g);
    }
}

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

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

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

[풀이]
2진수 문자열을 3개씩 나눠서 3개를 8진수의 한자리로 보고 변환해주면 0~7의 수로 바꿀 수 있다.

import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var n = readLine()
    n = n.reversed()
    val arr = listOf(1,2,4)
    var ans=StringBuilder()
    for(i in n.indices step 3){
        var t=0
        for(j in 0..2){
            if(i+j>=n.length) break
            t+=arr[j]*(n[i+j]-'0')
        }
        ans.append(t.toString())
    }
    println(ans.reverse())
}

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

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

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

[풀이]
수빈이의 위치와 동생들의 위치의 차이를 배열에 넣어놓고
유클리드 호제법을 이용해 모든 값에 대한 최대공약수를 구하면 된다.

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.*
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`))){
    val ip = readLine().split(' ')
    val N = ip[0].toInt()
    val S = ip[1].toInt()
    val arr = readLine().split(' ').map { abs(S-it.toInt()) }
    var prev=arr[0]
    for(a in arr) prev=gcd(a,prev)
    println(prev)
}

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

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